biPrimes/ZAA11

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

biPrimes/ZAA11
Ich kämpfe gerade ein bischen mit folgendem Problem:
Der Standard-Primzahltest(O(sqrt(n))) braucht zuviel Zeit.
Eratosthenes braucht zuviel Platz.
Liegt das daran, dass ich diese Algorithmen nicht effizient genug gebrauche, oder muss hier ein anderer Ansatz gewählt werden?
Ich frage, damit ich nicht ewig an einer Lösung herumdoktore, die sowieso aussichtslos ist.


Das ist korrekt und schon mal die erste Einsicht :wink: Du wirst keinen Standardalgorithmus finden, der dir das Problem effizient loest.

Deswegen: ueberleg dir mal, mit welchen schnellen/einfachen Tests man ausschliessen kann, dass eine Zahl prim ist. Vielleicht kannst du diese Tests fuer BiPrimes erweitern…


Du kannst dir denk ich zum Beispiel die Letzte Stelle anschauen. wenn da 2 0 oder 5 Steht kannstes schonmal als nicht prim einstufen.


kannst du um 4, 6, 8 erweitern :wink:


Genau das macht ja der sqrt(n) Algorithmus, oder bin ich schief gewickelt?
bool prime(int n) {
if (n < 2) return false;
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}


Das ganze heißt nicht umsonst „biPrimes“ :wink: les mal nochmal die Aufgabenstellung durch.


Ende auf 1 3 7 9(!!!) => komplett testen
Ende auf 2 5 => wenn einstellig Prim, sonst nicht
Ende auf 0 => nie Prim.


und auch nur Zahlen die damit anfangen können biprim sein :wink: abgesehen von den einstelligen


Und wenn’s ganz dumm läuft, muss man manche Aufgaben sogar selbst lösen :wink:


Danke an MeisterT.
@al.: sehr hilfreich…all diese erstaunlichen Erkenntnisse über Primzahlen…


Entschulgigung, wenn ich helfen wollte…passiert mir nicht nochmal…


Ich habe mal gehört, es ist ganz praktisch, sich zu bestimmten Aufgabengruppen die dazugehörigen HalloWelt-Folien durchzulesen. Man sagt, da gäbe es manchmal inhaltliche Zusammenhänge.


Ich beschwere mich nicht, dass man mir helfen möchte, ich freue mich selbstverständlich über Hilfe. Aber in diesem Fall sehe ich zwei Möglichkeiten: Entweder bin ich so dämlich, dass ich nicht sehe, wie diese Ratschläge den geposteten Standard-Algo schlagen;
In dem Fall bitte ich um Entschuldigung.
Oder mir wurde nur gesagt, was ich schon wusste. Dann sehe ich nicht die angebotene Hilfe.
Aber, langer Rede kurzer SInn: Was ich wissen wollte, habe ich erfahren, passt. Gut.


Die entscheidenden Tipps, die Aufgabe zu loesen stehen wirklich in den Posts (meiner war wahrscheinlich der am wenigsten zielfuehrende, weil ich dir was zum Denken uebrig lassen wollte). Daemlich wuerde ich dich deswegen aber nicht bezeichnen…


Konsequenterweise würde ich das.
Also: mea culpa, ich nehme alles zurück.


Konstante Faktoren kann man halt nur in der Theorie weglassen, …