primzahlen
-
Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Mathematik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
naja, eben dass man die anzahl der zu überprüfenden zahlen minimiert. also nicht bis zahl-1 überprüfen, das ist quark.
denn wenn man zahl durch irgendetwas zwischen zahl/2+1 und zahl teilt, so bekommt man als ergebnis nie etwas ganzzahliges. das ergebnis kann nur noch zwischen 1 und 2 liegen.
weiter kann man das dann eben noch einschränken, wie schon von volkard geschrieben, indem man nichtmal bis zahl/2 überprüft, sondern nur bis zur wurzel von zahl.
beispiel:zahl = 37
sqrt(zahl) ~ 6,1 also etwa 6
zahl/2 -> nicht ganzzahlig
zahl/3 -> auch
zahl/5 -> auch
-> 37 = primzahl
weiter muss ich nich überprüfen, denn wenn ich noch zahlen > 6.1 überprüfe, also z.b. 7, dann kann als ergebnis der division nur noch etwas kleiner als 6.1 herauskommen. und die zahlen haben wir schon überprüft.ich hoffe mal dass ich jetzt keinen quatsch geschieben hab!
-
naja, so ein matheass bin ich dann auch nicht
-
ja da hat nubian recht das sollte reichen !
also wenn da mehrere zahlen überprüft werden sollen, würde ich vorschlagen das "Sieb des Erathosthenes" empfehlen (ich weiss nicht ob das hier jemand kennt) also das is wenn man ne primzahl kennt, dann kann man alle vielfachen davon als primzahlen ausschliesen, also kann man einen boolvektor anlegen, der alle zahlen die primzahlen sind auf true hat.
dann beginnt man zb. in dem man einen vektor mit 100 boolelementen anlegt und dann beginnt man mit 2 denn 2 is ja eine primzahl, also schaltet man 4,6,8 und so weiter auf false....
dann macht man bei der nächsten zahl, die noch true(also eine primzahl ist) weiter, das wäre dann 3 und schaltet alle vielfachen von 3 auf false, also 6,9 und so weiter.
dann geht man zur nächsten zahl die true hat (also 5) und macht dort das selbe.
am ende hat man dann einen vektor bei dem alle primzahlen auf true sind und alle nicht-primzahlen auf false.
dann braucht man nur noch nach jeder eingabe prüfen ob der schalter mit dem index true oder false ist und dann hat man das ergebnis. also ich weiss wirklich nicht wie die laufzeit dabei is, aber ich denke wenn man jetzt 20 zahlen eingeben will und jedesmal durch alles teilen muss geht es mit dem vektor schneller, aber das is sicher ansichtssache.
naja ich hoffe es hat überhaupt jemand geblickt .....
vielleicht kanns ja jemand brauchen ....
mfg _Ocin_
-
das problem ist die größe des feldes un der speicherverbrauch.
dazu kommt noch, dass das anlegen des vectors(falls man die werte nicht selber eingibt) unter umständen recht lange dauern kann.
-
vector<bool> ist ganz sicher eine schlechte idee. die grösse des siebs ist eigentlich nicht das problem, man kann ja scheibchenweise sieben.
-
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 ....
-
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.
-
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)
-
ja ich weiss, ich war müde, und habe einiges verdreht.... Habt natürlich alle recht