10001-te Primzahl herausfinden

[ac]

hallo,

muss die 10001-te Primzahl herausfinden. Dazu habe ich folgenden Code geschrieben, der allerdings nicht terminiert. Könnte mir jmd. vtl. sagen, warum? Sehe nämlich den Fehler nicht:

public class Problem7{

	//prüft, ob Zahl gleich Primzahl
	
	static boolean prim(long n){
		
		if(n<=2){
			return (n == 2);
		}
		
		for(long i=2; i<=n; i++){
			
			if( (n%i) == 0){
				return false;
			}	
		}
		
		return true;
	}

	public static void main(String[] args){
		
		Problem7 pr = new Problem7();
		
		long test = 1;
		long zaehler = 0;
		long anzahlPrim = 0;
		
		while(test == 1){
			
			if(pr.prim(zaehler)){
				anzahlPrim +=1;
				zaehler +=1;
			}
			
			else{
				zaehler+=1;
			}
			if(anzahlPrim == 10001){
				System.out.println(zaehler);
				test = 0;
			}
		}
	}


}

 

[DrZoidberg]

Ändere mal die Zeile hier ab
[Java]for(long i=2; i<=n; i++){[/Java]
in
[Java]for(long i=2; i*i<=n; i++){[/Java]

 

[stg]

Der terminiert schon, nur nicht in der Zeit, die du dir wünscht und auch nicht mit dem von dir gewünschten Ergebnis!

Für

i=n

ist

n%i

stets 0 und damit wir ab der zwei gar keine Primzahl gefunden. Richtig wäre hier im Schleifenkopf

i<n

statt

i<=n

zu schreiben. Aber es reicht aus nur alle möglichen Teiler bis zur Quadratwurzel von

n

zu prüfen. Wenn du bis dahin keinen Teiler gefunden hast, dann gibt es danach auch keinen mehr! Damit kannst du die Laufzeit deines Codes schon einmal entscheidend verbessern.

Übrigens, die 10.0001ste Primzahl ist 104,743, so zur Kontrolle...

 

[ac]

vielen dank für die Hilfe...v.a. den Tipp mit der Quadratwurzel. Den hatte ich zwar irgendwo schonma gesehen, aber hatte nicht ganz verstanden warum man die Wurzel nehmen sollte. Jetzt weiß ichs.

edit: habe auch in Zeile 41 "....(zaehler - 1 ) " geschrieben...damit das richtige Ergebnis rauskommen soll. Wusste jez nicht ganz wieso ich am ende mit minus 1 rechnen soll, aber es hat geholfen auf das korrekte Endergebnis zu kommen.



gruß,
ac

 

[MrClave]

Du kannst zusätzlich Zeit sparen, indem du alle geraden Zahlen überspringst, und nur mit den ungeraden arbeitest.

for ( long i = 0; i * i <= n; i += 10 ) {

wenn i + 1 % 2 == 0 -> keine primzahl
wenn i + 3 % 2 == 0 -> keine primzahl
wenn i + 5 % 2 == 0 -> keine primzahl
wenn i + 7 % 2 == 0 -> keine primzahl
wenn i + 9 % 2 == 0 -> keine primzahl

}

PS:
Hier kannst du dir das else sparen, da du den Zähler so oder so inkrementierst.

if(pr.prim(zaehler)){
         anzahlPrim +=1;
           zaehler +=1;
   }      
   else{
        zaehler+=1;
   }

if ( pr.prim( zaehler ) ) {
anzahlPrim++;
}
zaehler++;

 

[stg]

...man kann natürlich noch viel, viel mehr optimieren. Ein Primzahlsieb bietet nochmals einen gewaltigen Geschwindigkeitsvorteil, da man sogar ganz ohne die eklige Modulo-Rechnerei auskommt. Außerdem haben alle Primzahlen größer als 3 die Form 6k±1 und man muss nur diese Zahlen testen usw.. je mehr Wissen man mitbringt, was die Mathematik hinter Primzahlen anbelangt, desto mehr kann man hier noch rauskitzeln. Man muss je nach Anwendungsfall natürlich immer noch abwägen, zwischen Speicherverbrauch und Laufzeit ... der wichtigste Optimierungsschritt ist aber der erste und bereits mehrfach genannte, dass nur bis zur Quadratwurzel von n auf Teilbarkeit geprüft wird, da hier tatsächlich das asymptotische Laufzeitverhalten entscheident verbessert wird, und nicht nur lediglich um einen konstanten Faktor.