Sind meine Primzahlenalgorithmen kompkt genug?
hi, ich hab einen der alle ausgibt und einen der eine zahl testet (ob sie prim ist).
(mein erster versuch an algorithmen)
5 Antworten
Du benutzt beim Ausgeben "aller" Primzahlen die gleiche Idee wie beim Prüfen einzelner Zahlen. Dadurch hast du Codeverdoppelung. Wenn dir irgendwann etwas besseres einfällt, musst an allen Stellen korrigieren.
Tipp 1: Mach aus deiner Methode void check(int a) eine boolean istPrim(int a) die true liefert, wenn a eine Primzahl ist. Sie sollte nichts in die Konsole schreiben (trenne Rechnung und Ausgabe, dann kannst du leichter in Dateien oder grafische Oberflächen ausgeben). In deiner Primzahlenliste kannst du istPrim(int a) wieder benutzen.
Tipp 2: Wenn du prüfen willst, ob 121 eine Primzahl ist, zählst du jetzt von 120 bis 11 herunter und machst 109 vergebliche Probedivisionen. Wenn du von unten nach oben zählst (ab 2 aufwärts) merkst du schon beim 10. Versuch, dass es keine Primzahl ist.
Tipp 3: Wenn du 127 prüfen willst, musst du nicht bis 126 probieren. Du kannst schon bei 12 aufhören.
Tipp 4: Um alle Primzahlen bis zu einer vorgegebenen Größe zu berechnen, ist das "Sieb des Eratosthenes" unschlagbar schnell.
Der erste sieht doch ganz ordentlich aus. Wenn ich mich nicht irre, wäre eine aufwärtszählende Schleife hier aber effizienter, da die Primzahldichte immer weiter abnimmt, wenn du verstehst, was ich meine. Wenn dich die mathematischen Hintergründe interessieren, gibt es da noch jede Menge weitere Beschleunigungen, etwa durch statistische Betrachtungen jener Primzahldichte usw. ...
Beim zweiten Algorithmus fällt mir aber sofort ins Auge, dass du zero immer weiter erhöhst, selbst wenn schon ein Teiler gefunden wurde - du könntest die Schleife in diesem Augenblick auch einfach mit break abbrechen!
Davon abgesehen noch ein paar Hinweise zur Codequalität:
- Die Aufteilung der Algorithmen würde ich noch mal überdenken. Die linke Klasse trägt als Bezeichnung ein Verb, was überhaupt nicht intuitiv ist, da eine Klasse ja ein Objekt repräsentieren sollte. Die rechte Klasse steht im Plural ... Sinnvoller wäre eine Bezeichnung PrimeChecker für beide zusammen. Klassen außerdem immer im PascalCase benennen.
- while(true)-Schleifen verwendet man eigentlich nur äußerst selten. In deinem Fall könntest du an dieser Stelle einfach ein for-Schleife über number verwenden, also: for (int number = 2; ; number++).
Komplett würde ich also calculate() im Optimalfall also wie folgt schreiben:
public static void calculate() {
infinity_loop:
for (int number = 2; ; number++) {
for (int i = number - 1; i > 1; i--)
if (number % i == 0) continue infinity_loop;
System.out.println(number);
}
}
(Dieses continue infinity_loop ist eine Kurzschreibweise dafür: Wenn number bereits einen Teiler hat, fahre sofort mit dem nächsten Schleifendurchlauf der äußeren Schleife, also für number = 3, fort.)
Das ist ein Label, das schreibt man so mit dem Doppelpunkt. Damit markierst du eine beliebige Schleife.
servus!
deine algorithmen sind sehr ineffizient, da du einen viel zu großen bereich überprüfst. von vornherein könntest du gerade zahlen auslassen, weil es sich bei denen (mit ausnahme der 2) niemals um eine primzahl handeln wird. (du kannst also in der schleife in zweier-schritten zählen)
negative zahlen kannst du ebenfalls weglassen und der maximal mögliche teiler ist maximal die wurzel aus deiner gesuchten zahl, also kannst du alle zahlen darüber von einer überprüfung ausschließen.
hier ist eine kurz zusammen gepfuschte lösung (die hoffentlich keinen fehler enthält):
public class Primes {
public static boolean isPrime(final long num) {
if (num < 2) {
return false;
} else if (num == 2) {
return true;
} else if ((num & 1) == 0) {
return false;
}
for (long i = 3; i*i <= num; i += 2) {
if((num % i) == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
for (long i = -2; i <= 20; ++i) {
System.out.printf(
"#%d: %b\n", i, isPrime(i)
);
}
}
}
das liefert für die zahlen von -2 bis +20 diese ausgabe:
#-2: false
#-1: false
#0: false
#1: false
#2: true
#3: true
#4: false
#5: true
#6: false
#7: true
#8: false
#9: false
#10: false
#11: true
#12: false
#13: true
#14: false
#15: false
#16: false
#17: true
#18: false
#19: true
#20: false
zum schluss muss ich aber sagen, dass java in der BigInteger-klasse einen mordsmäßig effizienten algorithmus implementiert hat, der dir blitzschnell und sehr sehr zuverlässig mitteilt, ob eine zahl prim ist, oder nicht:
import java.math.BigInteger;
public class Main {
public static boolean isPrime(final long num) {
return BigInteger.valueOf(num).isProbablePrime(1);
}
public static void main(String[] args) {
for (long i = -2; i <= 20; ++i) {
System.out.printf(
"#%d: %b\n", i, isPrime(i)
);
}
}
}
die isProbablePrime()-methode ist zwar nicht perfekt akkurat, aber für kleinere zahlen im long-bereich stimmen die ergebnisse zu 100%.
woher weißt du dass es keine teiler größer der wurzel der zahl gibt?
Wenn man von unten anfängt, muss man nur bis zur Wurzel gehen. Wenn du durch einen Teiler jenseits der Wurzel teilst, kommt ein Ergebnis heraus, das kleiner als die Wurzel ist. D.h. du hast vorher bereits gemerkt, dass es keine Primzahl ist.
Beispiel 91: Hat den Teiler 13. 91:13 = 7. Sieben hast du bereits geprüft.
@GuiseppePeano
VORSICHT!
Mit Parameter 1 liefert isProbablyPrime aber gaanz schlechte Ergebnisse.
Probier mal:
for (int i=0;; i++) {
if (isPrime(i) != isPrime2(i)) System.out.println(i);
}
Wobei isPrime klassisch bis zur Wurzel probiert und isPrime2 die Methode isProbablePrime aus BigInteger benutzt. isProbablePrime gibt manchmal auch zusammengesetzte Zahlen als möglicherweise prim aus. Umso häufiger, je kleiner der certainty Parameter ist. Wenn die Methode false liefert, ist es auf jeden Fall keine Primzahl, wenn sie true liefert, ist die Irrtumswahrscheinlichkeit 2^(-certainty) Bei certainty=1 ist die Hälfte der angeblichen Primzahlen falsch (laut Doku). Der certainty-Parameter muss also mit der Bitlänge der zu prüfenden Zahl wachsen.
Bei certainty-Parameter 5 braucht eine Schleife von 1 bis 10 Mio ca. 3x so lange wie die Probedivision und liefert dabei 2 falsche Primzahlen.
Bei wirklich großen Zahlen ist es deutlich schneller als die Probedivision.
Aber ich glaube, dem Fragesteller ging es weniger darum, Primzahlen zu finden, als selbst einen Algorithmus zu basteln. Und für einen Anfänger war das schon ganz gut, wenn auch nicht turboschnell.
oh, danke für den wichtigen hinweis! da habe ich so gar nicht dran gedacht!
Du kannst generell zuerst mal abprüfen, ob die Zahl ungerade ist und dann erst weitermachen.
Dann kannst Du den Schritt auf 2 seitzen und auf > 2 statt > 1 testen.
Du kannst in der for-schleife im Kopf das Int i weglassen und gleich mit a-1 anfangen.
Und woher weiß dann das Programm, was die Laufvariable sein soll und welchen Datentyp i hat?
Ja und? Daraus erzeugt aber kein Java-Compiler ungefragt ein "int i".
Hast du das ausprobiert?
okay vielen dank . und man schreibt doppelpunkt bei infinityloop?? das hat ja gar keinen variablentyp oder was ist das