Die Methode für den Primzahltest trägt den Namen
„isPrime”
und erwartet die Zahl
„number”
als Parameter.
Die Zahl
„number”
ist keine Primzahl, wenn sie geteilt werden kann, also wenn ein Teiler für number existiert.
Die Methode isPrime sucht deshalb einen Teiler, der ungleich 1 und ungleich der gegebenen Zahl number ist.
Wird ein solcher Teiler gefunden, ist die Zahl number keine Primzahl, andernfalls handelt es sich um eine Primzahl.
Zunächst muss man sich überlegen, welche Zahlen als Teiler in Frage kommen.
Der erste, allerdings recht naive Ansatz ist, dass man alle Zahlen zwischen 1 und number nimmt
und versucht number mit diesen Zahlen zu teilen
— die typische
Brute-Force-Vorgehensweise.
Zahlen, die kleiner als die kleinste Primzahl sind, kommen als Teiler nicht in Frage,
ebenso nicht die Zahlen, die größer oder gleich der gegebenen Zahl number sind.
Sehen Sie hierzu folgenden Algorithmus.
/**
* Naiver Primzahltest mit maximal (number-2) Teilertests.
*/
public class NaivePrimeTest1 {
/**
* Prüft, ob gegebene Zahl eine Primzahl ist.
* @param number Die gegebene Zahl.
* @return true, falls number Primzahl ist.
*/
public static boolean isPrime(int number) {
if (number < 2) {
// number ist keine Primzahl, 2 ist nämlich die kleinste Primzahl.
return false;
} else {
// Versuche number mit den Zahlen 2 bis number-1 zu teilen!
for (int i = 2; i < number; i++) {
// Teilertest: Ist number durch i teilbar?
if (number % i == 0) {
// Hier ist bewiesen, dass number keine Primzahl ist.
return false;
}
}
// number ist konnte nicht ganzzahlig geteilt werden,
// also ist number eine Primzahl.
return true;
}
}
}
Wenn es sich bei number um eine Primzahl handeln sollte, so werden fast number-viele potentielle Teiler durchprobiert
(2 bis number-1).
Um die Laufzeit zu beschleunigen, kann man versuchen, die Anzahl der Teilertests zu reduzieren.
Dies kann man erreichen, wenn man die Anzahl der potentiellen Teiler reduziert.
Nur mal angenommen, die gegebene Zahl number sei durch 2 teilbar, ergibt sich folgende Aussage:
number = 2 * (number / 2).
Nun kann man sich schnell plausibel machen, dass die Zahlen von
((number / 2) + 1)
bis
(number - 1)
keine Teiler für number sein können; der Teilungsrest für diese Zahlen ergäbe irgendetwas zwischen 1 und 2.
Dieser Ansatz verbessert den ersten Ansatz dergestalt, indem die Tests für den eben angeführten Zahlenbereich
((number / 2) + 1)
bis
(number - 1)
wegfallen.
Es stellt sich noch die Frage, ob auch der potentielle Teiler
(number / 2)
wegfallen kann.
Ist die Zahl number durch
(number / 2)
teilbar, dann auch durch 2.
Und da die potentiellen Teiler aufsteigend getestet werden,
würde der erste Teilversuch mit der 2, number schon als
Nicht-Primzahl
entlarven und gar nicht erst zum potentiellen Teiler
(number / 2)
vordringen.
Aus diesen Gründen, werden hier die potentiellen Teiler aus dem Zahlenbereich 2 bis
((number / 2) - 1)
getestet.
Sehen Sie hierzu folgenden Algorithmus.
/**
* Naiver Primzahltest mit maximal ((number/2)-2) Teilertests.
*/
public class NaivePrimeTest2 {
/**
* Prüft, ob gegebene Zahl eine Primzahl ist.
* @param number Die gegebene Zahl.
* @return true, falls number Primzahl ist.
*/
public static boolean isPrime(int number) {
if (number < 2) {
return false;
} else {
/* Versuche number mit den Zahlen 2 bis number/2 zu teilen! */
for (int i = 2; i < (number / 2); i++) {
if (number % i == 0) { // Teilertest
return false;
}
}
return true;
}
}
}
Die Teilertests sind mit dem zweiten Ansatz deutlich reduziert worden.
Es sind etwa
(number/2)-viele
Tests.
Noch mehr Effizienz holt man heraus, wenn man den zweiten Ansatz weiterdenkt.
Im zweiten Ansatz kommen die Zahlen größer als
(number / 2)
nicht als Teiler in Frage.
Dies kann man sich mit der Zahl 3 analog herleiten, so dass die Zahlen, die größer sind als
(number / 3),
nicht mehr als Teiler in Frage kommen, vorausgesetzt die 2 wird als Teiler getestet.
Und das Analoge mit der 4 und der 5 und so weiter bis
m = Quadratwurzel(number),
so dass
number = m * m.
Der zu testende Zahlenbereich ist jetzt von 2 bis
Quadratwurzel(number), sehen Sie hierzu folgenden Algorithmus.
/**
* Primzahltest mit maximal ((number^0.5)-1) Teilertests.
*/
public class PrimeTest {
/**
* Prüft, ob gegebene Zahl eine Primzahl ist.
* @param number Die gegebene Zahl.
* @return true, falls number Primzahl ist.
*/
public static boolean isPrime(int number) {
if (number < 2) {
return false;
} else {
/* Versuche number mit den Zahlen 2 bis sqrt(number) zu teilen! */
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) { // Teilertest
return false;
}
}
return true;
}
}
/**
* Wendet den Primzahltest auf die Zahlen von 1 bis 100 an und gibt die
* Primzahlen auf der Konsole aus.
* @param arguments Ohne Bedeutung.
*/
public static void main(String[] arguments) {
for (int z = 1; z <= 100; z++) {
if (isPrime(z)) {
System.out.println(z + " is prime.");
}
}
}
}
Man könnte nun annehmen, dass dieser Algorithmus das höchste aller Gefühle wäre.
Dem ist aber nicht so,
siehe vierter Ansatz.
Doch erst, sei dem Ungläubigen mit folgender Ausgabe gezeigt, dass der dritte Ansatz auch funktioniert.
:-)
2 is prime.
3 is prime.
5 is prime.
7 is prime.
11 is prime.
13 is prime.
17 is prime.
19 is prime.
23 is prime.
29 is prime.
31 is prime.
37 is prime.
41 is prime.
43 is prime.
47 is prime.
53 is prime.
59 is prime.
61 is prime.
67 is prime.
71 is prime.
73 is prime.
79 is prime.
83 is prime.
89 is prime.
97 is prime.
Die hier aufgelisteten Primzahlen sollten die ersten 25 Primzahlen sein.
Die Bestrebungen in diesem Ansatz laufen immer noch darauf hinaus, die Anzahl der Teilertests zu reduzieren.
Wie kann man also den zu testenden Zahlenbereich noch weiter einschränken, zumal die optimale Obergrenze
(Quadratwurzel(number))
schon bekannt ist?
Im dritten Ansatz war zwar eine drastische Verbesserung des Vorgängeransatzes zu verzeichnen,
doch wer das Sieb des Eratosthenes kennt,
wird sicherlich schon längst auf einen anderen Aspekt der Reduzierung der Teilertests gekommen sein.
Wir sieben!
Wenn nun alle
Nicht-Primzahlen
aus den zu testenden Zahlenbereich herausgesiebt werden würden, wäre die Anzahl der Teilertests minimal.
Doch das sieben ist aufwendig und auch gar nicht unkompliziert.
Die noch übrig gebliebenen Teilertest können ganz einfach halbiert werden,
indem die geraden Zahlen
(außer der Zahl 2)
herausfiltert werden.
Sehen Sie hierzu den folgenden Algorithmus.
/**
* Primzahltest mit maximal (((number^0.5)-1)/2) Teilertests.
*/
public class FasterPrimeTest {
/**
* Prüft, ob gegebene Zahl eine Primzahl ist.
* @param number Die gegebene Zahl.
* @return true, falls number Primzahl ist.
*/
public static boolean isPrime(int number) {
if (number < 2) {
return false;
} else if (number == 2) {
return true;
} else {
/* Versuche number mit der Zahl 2 zu teilen! */
if (number % 2 == 0) {
return false;
}
/* Versuche number mit den ungeraden Zahlen
von 3 bis sqrt(number) zu teilen! */
for (int i = 3; i <= Math.sqrt(number); i = i + 2) {
if (number % i == 0) { // Teilertest
return false;
}
}
return true;
}
}
/**
* Wendet den Primzahltest auf die Zahlen von 1 bis 100 an und gibt die
* Primzahlen auf der Konsole aus.
* @param arguments Ohne Bedeutung.
*/
public static void main(String[] arguments) {
for (int z = 1; z <= 100; z++) {
if (isPrime(z)) {
System.out.println(z + " is prime.");
}
}
}
}
Suchen Sie doch bitte noch nach weiteren Verbesserungen!
Die Laufzeitabschätzungen zur Brute-Force-Methode sind trotz der wenigen Teilertests dennoch exponentiell.
Grund:
Divisionen so wie Modulo-Rechnungen hängen von der Größe des Teilers ab.
Neben der hier vorgeführten
Brute-Force-Methode
gibt es auch stochastische Mittel und Methoden mit einer gewissen Ungenauigkeit einen effizienten Primzahltest durchzuführen.