Wie programmiere ich ein Primzahlenüberprüfer mit Lazarus?
Hallo,
wie erstelle ich auf Lazarus ein Programm, welches deine eingegebene Zahl überprüft, ob es eine Primzahl ist oder nicht - mit der Verwendung von dem Modulo (mod)?
Habt ihr Lösungsansätze/Lösungen?
3 Antworten
Schau mal hier:
https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests
Da finden sich auch Verfahren, die in Quasipolynominalzeit laufen und auch keinen Unmengen an Speicherplatz benötigen.
Kenne Lazarus nicht, aber den Algorithmus:
Fange bei i = 2 an. Deine Zahl heißt N.
- Prüfe, ob i² > N. Wenn ja ist N eine Primzahl.
- Prüfe, on N % i == 0 ist. Wenn ja, ist N keine Primzahl
- Erhöhe i um 1
- Fahre bei Punkt 1 fort.
Ist nicht der schönste, aber verbessern kann man fast immer.
% ist der Modulo-Operator
== ist der Vergleich auf Gleichheit
Du überprüfst in einer Schleife, ob die Zahl n durch [2; n/2] teilbar ist bzw. gleich 0 oder 1 ist (das sind keine Primzahlen). Wenn bei irgendeinem dieser Werte n % ... = 0 ist, weißt du, dass die Zahl keine Primzahl ist.
Wie man das in Pascal implementiert kann ich dir nicht sagen. Die Schleife würde in C++ aber so aussehen:
for (int i = 2; i <= n/2; i++) {
if (n % i == 0) // keine primzahl
}