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: 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 | ||||||
|
|
||||||
|
|
