Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Hallo!
Ich soll ein Programm schreiben,dass prüft ob bestimmte Zahlen Primzahlen sind,dabei soll die Methode einen boolean zurückgeben
Ich bin leider noch ein Anfänger und weiß leider gar nicht was ich da falsch gemacht habe.Das Programm funktioniert auch leider nicht.
Das nennt sich "vollständige Induktion": Verankerung: n=1 ist eine Primzahl Induktionsschritt: n+1=2 ist eine Primzahl Induktionssschluss: Alle Zahlen sind Primzahlen
:joke:
Das nennt sich "vollständige Induktion": Verankerung: n=1 ist eine Primzahl Induktionsschritt: n+1=2 ist eine Primzahl Induktionssschluss: Alle Zahlen sind Primzahlen
:joke:
public static boolean istPrim(int n){
boolean primZahl=true; //... solange wir keinen Teiler gefunden haben
int moeglicherTeiler = 2;
while(moeglicherTeiler < n){ //Teiler muss kleiner sein als Zahl selbst
if(n % moeglicherTeiler==0) { //Teiler gefunden -> keine Primzahl
primZahl=false;
}
moglicherTeiler = moeglicherTeiler + 1; //Teiler hochzählen
}
return primZahl;
}
Das sollte funktionieren, lässt sich aber in vieler Hinsicht verbessern:
- eine bessere obere Schranke ist sqrt(n)
- beim ersten gefundenen Teiler kann die Schleife bereits verlassen werden
- man braucht Teilbarkeit durch gerade Zahlen außer 2 nicht zu testen
Mitunter am effektivsten ist es wahrscheinlich, wenn du eine Liste erstellst, wo alle bereits gefundenen Primzahlen reinkommen.
Für jedes n versuchst du dann, dieses restlos durch jede der Zahlen in der Liste (in aufsteigender Reihenfolge) zu teilen.
Findest du keinen Teiler, ist n eine Primzahl (und kommt dann auch in die Liste).
Dazu noch als obere Schranke sqrt(n) und du bist schon relativ fix unterwegs
Das sollte funktionieren, lässt sich aber in vieler Hinsicht verbessern:
- eine bessere obere Schranke ist sqrt(n)
- beim ersten gefundenen Teiler kann die Schleife bereits verlassen werden
- man braucht Teilbarkeit durch gerade Zahlen außer 2 nicht zu testen
Punkt 1: Angenommen der kleinste echte Teiler a einer zusammengesetzten Zahl n wäre größer als sqrt(n). Sei b = n / a. Dann ist b ebenfalls ein echter Teiler von n, und nach Voraussetzung ist b mindestens so groß wie a, also ebenfalls größer als sqrt(n). Aus a > sqrt(n) und b > sqrt(n) folgt a*b > n, Widerspruch!
Also muss von den Teilern einer zusammengesetzten Zahl mindestens einer kleiner als deren Wurzel sein.
Punkt 3: Wenn eine Zahl n nicht durch eine Zahl k teilbar ist, ist sie auch nicht durch Vielfache von k teilbar. Die geraden Zahlen sind Vielfache von 2.
Punkt 1: Angenommen der kleinste echte Teiler a einer zusammengesetzten Zahl n wäre größer als sqrt(n). Sei b = n / a. Dann ist b ebenfalls ein echter Teiler von n, und nach Voraussetzung ist b mindestens so groß wie a, also ebenfalls größer als sqrt(n). Aus a > sqrt(n) und b > sqrt(n) folgt a*b > n, Widerspruch!
Also muss von den Teilern einer zusammengesetzten Zahl mindestens einer kleiner als deren Wurzel sein.
und, frage 1: ist jede nicht-primzahl eine zusammengesetzte zahl? 2: warum folgt aus b=n/a das b ebenfalls teiler von n ist? den rest versteh ich ja...
1: Ja. Zumindest in den ganzen Zahlen (bzw in Hauptidealringen), aber ich denke darum geht es hier
2: Wenn b=n/a ist, dann ist n = a*b, also b ein Teiler von n...