Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Primzahlen finden - welche Komplexität? » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Zum Ende der Seite springen Primzahlen finden - welche Komplexität?
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
igor789
unregistriert
Primzahlen finden - welche Komplexität? Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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?
30.05.2016 22:35
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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++){

__________________
Syntax Highlighting fürs Board (Link)
31.05.2016 06:48 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
igor789
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
31.05.2016 19:31
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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]

__________________
Syntax Highlighting fürs Board (Link)
31.05.2016 22:36 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Informatiker Board » Themengebiete » Praktische Informatik » Primzahlen finden - welche Komplexität?