Primzahlen finden - welche Komplexität? |
30.05.2016, 22:35 | Auf diesen Beitrag antworten » | |||||
igor789 | Primzahlen finden - welche Komplexität? Moin, mal aus Interesse folgende Frage: Hier mal ein Java Programm zum Finden von Primzahlen:
Ist meine Annahme richtig, dass das Programm n*((n^2+n)/2) Schritte benötigt um zu terminieren? |
|||||
|
||||||
31.05.2016, 06:48 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Ich komme auf . Die Summe mit i als Index ist die Schleife aus getPrimeTo. Die innere Summe ist die von teilbarQ. Dort wird immer eine Division durchgeführt. Das gibt 1/2*n^2 - 3/2*n + 1 Du könntest die Laufzeit übrigens verkürzen: Mache in teilbarQ aus for(int i=2;i<n;i++){ das hier: for(int i=2;i*i<=n;i++){ |
|||||
31.05.2016, 19:31 | Auf diesen Beitrag antworten » | |||||
igor789 | Hi, danke für den Tipp, das stimmt natürlich. Gibt es eigentlich einen schnelleren Algorithmus hierfür? Kommt man irgendwie um die 2 Schleifen rum? Und nochmal zur Laufzeit: wie schließt du von diesem Ausdruck auf 1/2*n^2 - 3/2*n + 1? Liebe Grüße |
|||||
31.05.2016, 22:36 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Wenn du alle Primzahlen bis zu einer bestimmten Grenze finden willst, gibt es das Sieb des Eratosthenes. Das braucht aber ordentlich Speicher. Alternativ das Sieb von Atkin. Zur Summenformel: ich habe sage (ein Mathematikprogramm) genommen. Geht aber auch so: |
|||||
Anzeige | ||||||
|
|