primzahlen berechnen

[blax]

ich suche den perfekten algorithmus um primzahlen zu berechnen
was besseres als

for(int i=3; i<limit; i+=2){
for(int j=i; i>2; i--){
if(i%j==0){
break; //is keine primzahl
}
}
}

fällt mir so spontan nicht ein.
gibts da was professionelleres?

[Stone2001]

Vielleicht hilt dir dieser Thread weiter: http://www.forum-3dcenter.org/vbulletin/showthread.php?t=95859&highlight=Primzahlen

[Mike]

eine optimierung wäre, das du i nicht durch alle Zahlen <i teilst, sondern nur durch alle zahlen <= Wurzel i..

eine suche nach "algorithmen primzahlen" etc wird bestimmt auch "professionelle" Lösungen finden...

[Gast]

ich suche den perfekten algorithmus um primzahlen zu berechnen
was besseres als

for(int i=3; i<limit; i+=2){
for(int j=i; i>2; i--){
if(i%j==0){
break; //is keine primzahl
}
}
}

fällt mir so spontan nicht ein.
gibts da was professionelleres?

Da wäre erstmal die Frage, was du überhaupt machen möchtest? Eine einzelne oder mehrer große Primzahl finden? Weil das würde dann etwas anders ablaufen ;)

-frank

[Gast]

ja..mein beispiel war kein ausprogrammiertes Programm (wie man sieht) und sollte einglich nur den Aufwand meines verfahrns verdeutlichen..dass der eigentlich fast quadratisch ist

[blax]

sry, der gast gerade war ich
Natürlich ist mein ziel unendlich große primzahlen möglichst schnell berechnen zu können :)

[littlejam]

for(int i=3; i<limit; i+=2){
for(int j=i; i>2; i--){
if(i%j==0){
break; //is keine primzahl
}
}
}

Hm ich find den Algo so wie er da steht nicht gut, kann mir auch nicht vorstellen dass der so funktioniert.
Wenn ich keinen Denkfehler habe, müssten in der 2. For-Schleife die beiden letzten "i"s gegen "j" getauscht werden und das j=i gegen j=sqrt(i) getauscht werden.
Des weiteren kannst du damit keine Primzahlen finden, es fehlt die Ausgabe bzw. ein Test ob die For-Schleife durch ist oder abgebrochen wurde.

For-Schleifen finde ich persönlich schwer lesbar und würde eher auf while zurückgreifen.
Schneller ists auch, wenn du dir bereits gefundene Primzahlen speicherst und nur noch auf diese testest.

Aber das steht schon in dem von Stone erwähnten Fred.

Gruß

[Shink]

Weiss jetzt nicht, ob das im anderen Thread schon vorgekommen ist oder ob das hier was bringt, aber: Die einfachste Methode, viel schneller Primzahlen auszuspucken, ist, Zahlen nur durch Primzahlen zu dividieren.

D.h. etwas in der Art: (pseudocode)

Container c = new Container<int>;
boolean prime = true;
c.add(2);
for (int i = 3; i < grenze; i+=2) {
prime = true;
for (int j = 0; j < c.length) {
if (j%(c.get(j)) == 0) {
prime = false;
break;
}
}
if (prime) c.add(i);
}

Das einzige Problem ist, dass c irgendwann nicht mehr im Speicher platz hat.

[ethrandil]

Um große Primzahlen zu bestimmen, kann man bestimmte Kandidaten 'raten' und dann darauf testen ob sie Primzahlen sind.
Die schnellen Methoden geben dabei zwar nur eine gewisse Wahrscheinlichkeit an ob die Zahl wirklich prim ist, diese lässt sich aber weit unter 99,9% drücken.

- Eth

[Gast]

Um große Primzahlen zu bestimmen, kann man bestimmte Kandidaten 'raten' und dann darauf testen ob sie Primzahlen sind.
Die schnellen Methoden geben dabei zwar nur eine gewisse Wahrscheinlichkeit an ob die Zahl wirklich prim ist, diese lässt sich aber weit unter 99,9% drücken.

- Eth
So schaut es aus - man "rät" eine große Primzahl und testet diese dann mit MonteCarlo Algorithmen. Das geht halbwegs flott und kann man auch bis auf exakte 100% Sicherheit bringen, wenn man denn den Rechenaufwand nicht scheut.

-frank