Primzahltest in Java, Hilfe beim Programmieren für Anfänger
Hallo, unser Informatik Kurs in der Schule lässt jeden Schüler sein eigenes, vom Lehrer vorbestimmtes, Thema präsentieren. Meins sind die Primzahltests in Java. Das Problem, die Themen, die wir bekommen müssen wir in Java auch vorführen. Allerdings verstehen viele das bestimmte Thema nicht, genauso wie bei mir, bzw. nicht wie ich es in Java schreibe. Hier ist die Aufgabenstellung meiner Lehrerin: **"Schreiben Sie ein Java Programm „Primzahltest“, das feststellt, ob die natürlichen Zahl n eine Primzahl ist. Ein einfaches – wenngleich ineffektives – Verfahren ist, die Zahl durch die Zahlen 2, 3, ... n zu teilen und zu überprüfen, ob dabei der Rest Null ist. Das Programm sollte die Ergebnisse ausgeben, damit die Zuhörer sehen können, zu welchem Ergebnis Java kommt. Denken Sie an eine sinnvolle Kommentierung ihres Programms und erstellen Sie ein Struktogramm." ** Nun meine Frage: Weiß jemand wie ich das programmieren muss? Ich denke, dass ich die Probedivision dafür nutzen soll, aber wie geht diese in Java?
3 Antworten
Du musst eine Schleife machen, die die zu Testende Zahl nacheinander durch alle kleineren Zahlen teilt, aber nicht mit dem / operator, sondern mit dem teilen, das den "Rest" ausgibt. (Ich glaub das ist der Mod (für modulo) Operator.) Wenn es keinen Rest gibt (dieser 0 ist), dann ist die Zahl teilbar und somit keine Primzahl. For (int counter=2; counter++; counter < zahl){
if(zahl % counter==0) then abbruch;
} % ist eine Abkürzung für den modulo Operator.
Da das Programm noch ständig ausgeben soll, was es tut, kannst du in die If bedingung noch ein else system.out.println(zahl+' geteilt durch '+counter+' ergibt den rest '+zahl%counter+' und ist somit (bisher) keine Primzahl!');
Das macht dann beim beispiel 121 neun mal mal eine textausgabe (121 mod 2 ergibt den rest 1..., 121 mod 3 ergibt den rest..., 121 mod 4 erginbt...) bis schließlich bei 121 % 11 0 rauskommt und die abbruch-sache passiert. was dann kommt musst du machen :)
Hier noch der Wiki artikel zum thema modulo:
Ein einfaches – wenngleich ineffektives – Verfahren ist, die Zahl durch die Zahlen 2, 3, ... n zu teilen und zu überprüfen, ob dabei der Rest Null ist.
Du musst nur bis zur Zahl (n-1) testen, jede Zahl ist glatt durch sich selbst teilbar, ansonsten steht in dem Zitat schon alles, was du machen musst. Feststellen, ob eine Zahl durch eine andere teilbar ist, kannst du mit dem Modulo-Operator ermitteln http://www.datenschwamm.de/4/java_grundkurs.php?p=modulo#modulo
Es würde schon reichen bis sqrt(n) zu überprüfen, da die Teiler entweder die Wurzel sind bei Quadratzahlen oder sonst mindestens einer darunter und einer darüber liegt
Ist richtig, nach der 2 müsste er auch nur ungerade Zahlen testen und wenn modulo bei einem Durchlauf nicht 0 ergibt, dann kann er die Prüfung für diese Zahl abbrechen... von solchen Optimierungen hab ich nur abgesehen, um das für den Fragesteller nicht noch komplizierter zu machen.
alle Primzahlen bis ⌊sqrt(n)⌋, wenn man sie schon kennt, sollten genügen.
Die kennt man aber nicht, müsste sie also erst berechnen. Ein Programm, das so rechnet, würde deutlich länger brauchen. Und es ist ja nicht Sinn der Sache, dass der Fragesteller schon eine Liste mit Primzahlen in dem Programm vorgibt.
Ein Eratosthenes- bzw. Atkin-Sieb wäre sogar noch schneller. Das ist hier aber alles nicht die Frage, lasst den Fragesteller doch erstmal einen allgemeinen Primzahltester fertigstellen, danach kann er über Optimierungen nachdenken. ;)
public static boolean isPrim(long n) {
if (n <= 2)
return true;
for (long i = 2; i <= n/2; i++)
if (n % i == 0)
return false;
return true;
}
das gilt natürlich nur für n > 0!
Vielen Dank für die schnelle Antwort. Das bildliche Vorstellen der Syntax wird mir nicht ganz klar, liegt auch daran, dass wir noch nie mit Modulo gearbeitet haben. Falls es dir nichts ausmacht, würdest du mir ungefähr zeigen, wie diese Syntax aufgebaut ist?