An alle Informatiker und Mathematiker

[mj]

Hi an alle Informatiker und Mathematiker...<br><br>Ich hoffe einer von euch kann mir helfen:<br>Ich bräuchte einen Algorithmus mit dem ich alle n-stelligen Primzahlen berechnen kann.<br><br>Ich hab mir zwar schon einen ausgedacht, aber der wäre ziemlich rechenintensiv. Gibt es eine &quot;leichte&quot; Methode alle n-stelligen Primzahlen auszurechnen?<br><br>Wenn niemandem so ein Algorithmus bekannt ist, gibt es vielleicht bereits ein existierendes Programm welches mir das erledigt? Lieber wäre mir allerdings ein Algorithmus.

[Stuffi]

weiss nicht ob das reicht, hab schonmal ein solches programm geschrieben - komm aber erst Mitte nächster Woche nach Hause.<br><br>http://www.google.de/search?q=cache:Yx0P3-pEn-8:wwwmath.uni-muenster.de/math/inst/logik/publ/lec/Pohlers/hbook.pdf+n-stellige+primzahlen+errechnen&amp;hl=de&amp;lr=lang_de<br><br>

[r-bitch]

na wie gross sollte denn Dein &quot;n&quot; sein?<br><br>für kleine n kann man ja selbst was schreiben (sollte denk ich iterativ sein, weil sonst zu gross), denke Dein prog geht da schon<br><br><br>..und für recht grosse (so n=80) geht man da glaub ich mit zufall und wahrscheinlichkeit ran:<br><br>LEHMAN-ALGORITHMUS:<br>{<br>wähle eine ungrade Zahl p <br>wähle eine Zufallszahl a kleiner als p (p ist die Primzahl) <br>Berechne a(p-1)/2 mod p <br>Ist a(p-1)/2 &amp;#8800; 1 oder -1 (mod p), so ist p definitiv nicht prim <br>Ist a(p-1)/2=1 oder -1 (mod p), so liegt die Wahrscheinlichkeit, daß p nicht prim ist bei höchstens 50 Prozent<br>}<br><br>ich glaub der Rabin-Miller-Algorithmus ist da noch genauer, aber da schau einfach mal in 'ner suchmaschiene vorbei

[mj]

Hmm... mein n wäre zw. 10 und 25 groß denke ich, mehr will ich nicht machen, sonst dauert die Berechnung zu lange....<br><br>Was ich mir überlegt hatte wäre ein Algorithmus, der die erste n-stellige Zahl als Standard hat, und dann, beginnend bei m=2 eine Berechnung durchführt:<br><br>n/m<br><br>Hat das Ergebnis Nachkommastellen, dann wird m um eins erhöht (m++) und die Berechnung erneut durchgeführt.<br>Sobald m &lt; n und das Ergebnis keine Nachkommastelle enthält, wird anschließend m wieder auf 2 gesetzt, und n = n+1 gesetzt, und die Berechnung wieder durchgeführt.<br><br>So geht das dann weiter, bei einem 10-stelligen n wäre das dann also von 1.000.000.000 bis 9.999.999.999<br>Wie du dir vorstellen kannst ist bereits das ganz schön zeitaufwendig... und jetzt stell dir erstmal vor wie das bei 25 Stellen wäre.<br>Leider nutzt mir ein Wahrscheinlichkeitsalghoritmus nicht viel, weil er einfach zu ungenau ist. Ich brauche die Primzahlen für eine Verschlüsselung.