primzahlen

camper

vector<bool> ist ganz sicher eine schlechte idee. die grösse des siebs ist eigentlich nicht das problem, man kann ja scheibchenweise sieben.

_Ocin_

ja ich hab ja gesagt das das mit der laufzeit und dem speicherplatz ne andere frage is aber ich wollt einfach nur mal posten, wie es gemacht werden kann, denn ich denke wenn ich dann unmengen an zahlen prüfen will, dauert das mit dem teilen jedesmal bestimmt noch länger.
auserdem bin ich selber noch nicht so lange im geschäft
und deshalb lass ich mich da auch gerne korrigieren ....

henselstep

Nach dem kleinen Fermatschen Satz ist (2^b-2)mod b=0, wenn n eine Primzahl ist. Und das Tolle: In fastz allen anderen Fällen erhältst du eine Zahl ungleich Null. Wenn du nun b=2 setzt, hast du einen schnellen Test, um die meisten Zahlen als nicht-prim zu entlarven. Dummerweise kann das Verfahren aber bei sogenannten Pseudoprimzahlen versagen. Musst dann also immernoch testen, sollte der Wert doch Null sein.

sqrt(zahl)

SUPER IDEE!

Satz von Fermat lautet:

p Primzahl mit ggt(a,p)=1. Dann ist a^(p-1) mod p = 1;

was du meinst ist das Berechnen des Inversen also:

ggt(a,n)=1 und (ax) mod n=1, dann gilt, falls n prim ist x = a^(n-2) mod n.

asmodis

henselstep schrieb:

Nach dem kleinen Fermatschen Satz ist (2^b-2)mod b=0, wenn n eine Primzahl ist. Und das Tolle: In fastz allen anderen Fällen erhältst du eine Zahl ungleich Null. Wenn du nun b=2 setzt, hast du einen schnellen Test, um die meisten Zahlen als nicht-prim zu entlarven. Dummerweise kann das Verfahren aber bei sogenannten Pseudoprimzahlen versagen. Musst dann also immernoch testen, sollte der Wert doch Null sein.

Du hast da wohl etwas schnell getippt.
Kleiner Satz von Fermat:
Falls p eine Primzahl und p teilt nicht a, gilt: a^(p-1) = 1 (mod p)

Um nun zu überprüfen, ob eine beliebige Zahl n eine Primzahl ist, berechnet man zum Beispiel

bool isPrim = (2^(n-1) MOD n) == 1;

Wenn nun false herauskommt, kann man sicher sein, dass n keine Primzahl ist.
Wenn aber true herauskommt, kann man nicht sicher sein, ob man wirklich eine Primzahl hat (Beispiel: 561)

henselstep

ja ich weiss, ich war müde, und habe einiges verdreht.... Habt natürlich alle recht