Primzahl prüfen
Die Prüfung, ob eine Zahl prim (also eine Primzahl) ist, muss nur bis zur Quadratwurzel durchgeführt werden (=optimierter Primzahltest).
Eine kurze Erklärung hierzu wird durch eine einfache Implementierung ergänzt. So kann man schnell prüfen, ob eine Zahl eine Primzahl ist.
Eine Zahl ist prim, wenn sie größer als 1 ist und es keine Zahl außer der 1 und sie selbst gibt, durch welche sie ganzzahlig teilbar ist.
Zunächst scheint es so, als müsse man also für jede Zahl x prüfen, ob es irgendeine Zahl i von 2 bis x-1 gibt, durch welche x ganzzahlig teilbar ist, um festzustellen, ob x prim ist.
Tatsächlich reicht es aber völlig aus, bis zur Quadratwurzel zu prüfen, denn für jede Zahl i, durch die x ganzzahlig teilbar ist und die größer als die Quadratwurzel ist, gibt es zwangsläufig eine Zahl j, die kleiner als die Quadratwurzel ist und durch die x ebenfalls ganzzahlig teilbar ist, denn i*j=x (teile ich x durch j, kommt eben ein ganzzahliges Ergebnis kleiner der Quadratwurzel heraus).
Wenn nun auf der Suche bis zur Quadratwurzel kein solches i gefunden wurde, so kann man daraus eindeutig schlußfolgern, daß es auch oberhalb der Quadratwurzel kein solches j gibt.
Hier eine einfache Umsetzung des Algorithmus:
Einfacher Primzahltest Algorithmus
/**
* Primzahl prüfen (Primzahltest)
*/
public static boolean isPrim(final long value) {
if (value <= 2) {
return (value == 2);
}
for (long i = 2; i * i <= value; i++) {
if (value % i == 0) {
return false;
}
}
return true;
}
Eine weitere Optimierungsmöglichkeit wäre, die Primzahlen bis zu einer gewissen Obergrenze vorrätig zu halten.
Selbstverständlich ergibt dies nur dann Sinn, wenn sehr häufig Zahlen bis zu dieser Obergrenze auf Ihre prim-Eigenschaft geprüft werden sollen.
Eine ebenfalls einfach zu implementierende Optimierung berücksichtigt, daß alle Zahlen, die weder durch 2 noch durch 5 teilbar sind, zwangsläufig auch nicht durch alle größeren Zahlen teilbar sind, die mit 2,4,5,6,8 oder 0 enden. In der Schleife müssen also nach der zwei und der fünf nur noch diejenigen Teiler ausprobiert werden, die mit den Ziffern 1,3,7 und 9 enden.
Eine solche Implementierung wird etwas länger, dafür aber auch deutlich performanter:
Effizienter Primzahltest
/**
* Primzahl prüfen (Primzahltest)
*/
public static boolean isPrim(final long value) {
if (value <= 16) {
return (value == 2 || value == 3 || value == 5 || value == 7 || value == 11 || value == 13);
}
if (value % 2 == 0 || value % 3 == 0 || value % 5 == 0 || value % 7 == 0) {
return false;
}
for (long i = 10; i * i <= value; i += 10) {
if (value % (i+1) == 0) { // 11, 21, 31, 41, 51, ...
return false;
}
if (value % (i+3) == 0) { // 13, 23, 33, 43, 53, ...
return false;
}
if (value % (i+7) == 0) { // 17, 27, 37, 47, 57, ...
return false;
}
if (value % (i+9) == 0) { // 19, 29, 39, 49, 59, ...
return false;
}
}
return true;
}
Eine simple Performance-Messung hat ergeben, daß der letzte Algorithmus bei Zahlen in der Größenordnung um 100.000.000.000.000 knapp um den Faktor drei schneller ist (er benötigt circa 36% der Rechenzeit des ersten Algorithmus), um eine Primzahl als solche zu erkennen. Bei Zahlen mit relativ kleinen Teilern sind beide Algorithmen nahezu identisch schnell. Der zweite Algorithmus spielt seine Stärke bei (großen) Primzahlen und bei Zahlen mit ausschließlich großen Teilern aus (also insbesondere auch bei Zahlen, die das Produkt zweier großer Primzahlen sind).
Ein weiterer Artikel, der zeigt, wie man in Java einfache Algorithmen programmieren kann, behandelt das Thema Fibonacci-Zahlen.
Nach oben, Inhaltsverzeichnis, Impressum |
Admin: Artikel editieren |