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

Informatiker Board » Themengebiete » Praktische Informatik » Primzahlen finden - welche Komplexität? » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 4 Beiträge
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]
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
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++){
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?