An alle Informatiker und Mathematiker

Hi an alle Informatiker und Mathematiker...

Ich hoffe einer von euch kann mir helfen:
Ich bräuchte einen Algorithmus mit dem ich alle n-stelligen Primzahlen berechnen kann.

Ich hab mir zwar schon einen ausgedacht, aber der wäre ziemlich rechenintensiv. Gibt es eine "leichte" Methode alle n-stelligen Primzahlen auszurechnen?

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.

weiss nicht ob das reicht, hab schonmal ein solches programm geschrieben - komm aber erst Mitte nächster Woche nach Hause.

http://www.google.de/search?q=cache...primzahlen+errechnen&hl=de&lr=lang_de

na wie gross sollte denn Dein "n" sein?

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


..und für recht grosse (so n=80) geht man da glaub ich mit zufall und wahrscheinlichkeit ran:

LEHMAN-ALGORITHMUS:
{
wähle eine ungrade Zahl p
wähle eine Zufallszahl a kleiner als p (p ist die Primzahl)
Berechne a(p-1)/2 mod p
Ist a(p-1)/2 ≠ 1 oder -1 (mod p), so ist p definitiv nicht prim
Ist a(p-1)/2=1 oder -1 (mod p), so liegt die Wahrscheinlichkeit, daß p nicht prim ist bei höchstens 50 Prozent
}

ich glaub der Rabin-Miller-Algorithmus ist da noch genauer, aber da schau einfach mal in 'ner suchmaschiene vorbei

Hmm... mein n wäre zw. 10 und 25 groß denke ich, mehr will ich nicht machen, sonst dauert die Berechnung zu lange....

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:

n/m

Hat das Ergebnis Nachkommastellen, dann wird m um eins erhöht (m++) und die Berechnung erneut durchgeführt.
Sobald m < 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.

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
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.
Leider nutzt mir ein Wahrscheinlichkeitsalghoritmus nicht viel, weil er einfach zu ungenau ist. Ich brauche die Primzahlen für eine Verschlüsselung.