Primzahlen finden - welche Komplexität?

Neue Frage »

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:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
public void getPrimeTo( int n){
		
		int zaehler=0;
		
		for(int i=2;i<=n;i++){
			if(teilbarQ(i)==false){
				
				zaehler++;
				
				
			}
		}
		System.out.println("Es gibt "+zaehler+ "Primzahlen bis " +n);
		
		
		}
	
	public boolean teilbarQ(int n){
		
		for(int i=2;i<n;i++){
			if(n%i == 0){
				return true;
			}
		}
		return false;


Ist meine Annahme richtig, dass das Programm n*((n^2+n)/2) Schritte benötigt um zu terminieren?
 
Auf diesen Beitrag antworten »
eulerscheZahl

Ich komme auf [latex]\sum_{i=2}^n\sum_{j=2}^{i-1}1[/latex].
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++){
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: [latex]\sum_{i=2}^n\sum_{j=2}^{i-1}1[/latex] wie schließt du von diesem Ausdruck auf 1/2*n^2 - 3/2*n + 1?

Liebe Grüße
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:
[latex]\sum_{i=2}^n\sum_{j=2}^{i-1}1= \sum_{i=2}^n(i-2) = \sum_{i=0}^{n-2}i = \frac{(n-2)(n-1)}{2}=\frac 1 2 n^2-\frac 3 2 n + 1[/latex]
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »