Querdenkender Webworker mit WordPress-Affinität

Primzahlen mit dem Sieb des Eratosthenes

Wofür sind Primzahlen eigentlich gut, außer das man von ihnen weiß, dass sie nur durch 1 und sich selbst teilbar sind? Über Primzahlen an sich gibt es eine Menge Stoff zu lesen und einiges zu lernen. Ihren Einsatz finden Primzahlen vor allem in der Kryptographie. Genauer will ich darauf aber nicht eingehen. Mich interessiert an den Primzahlen vor allem, wie man sie herausbekommt. Es gibt einige moderne Algorithmen, die naturgemäß besser geeignet sind. Aber die älteste bekannte Methode ist das Sieb des Eratosthenes, die jedoch eher für einen kleineren Zahlenbereich (bis etwa 10.000.000) gedacht ist.

Der Algorithmus wird so implementiert, dass man eine Liste mit Zahlen aufbaut, die bei der ersten bekannten Primzahl (nämlich der 2) beginnt. Danach wird für jede Zahl in der Liste geprüft, ob andere Zahlen in der Liste durch diese teilbar sind. Trifft das zu, werden diese Zahlen entfernt. Es muss außerdem angemerkt werden, dass die Prüfung nur dann vorgenommen wird, wenn das Quadrat des Divisors nicht größer ist als die Zahl, die gerade überprüft wird. Im Netz kursieren einige Code-Beispiele, die entweder nicht funktionieren oder direkt auf der rekursiven C-Implementierung beruhen. Allerdings lässt sich dieser Algorithmus auch hervorragend für die Demonstration der Funktionsweise von array_walk benutzen:

[code lang=“php“]
function eratosthenes (&$item, $key, $value) {
if (sqrt ($item) >= $value && $item % $value == 0) {
$item = FALSE;
}
}

function primes ($max) {
$pArr = array ();
if (is_int ($max) && $max > 1) {
$pArr = range (2, $max);
foreach ($pArr as $n) {
array_walk ($pArr, ‚eratosthenes‘, $n);
$pArr = array_filter ($pArr);
}
}
return array_values ($pArr);
}

print_r (primes (100));
[/code]

Die Funktion primes nimmt einen Integerwert entgegen, der den maximalen Wert in der Liste darstellt. Daraufhin wird mit range das Array aufgebaut. In der Schleife, die jeden Wert der aktuellen Liste durchläuft, wird array_walk mit dem Callback an eratosthenes aufgerufen. Da diese Callback-Funktion eine Referenz auf das Listenelement enthält, wird bei Übereinstimmung der Abfrage auf Teilbarkeit, dieses direkt mit FALSE markiert. Danach erfolgt eine Filterung der Liste, die dann nur noch die übriggebliebenen Werte enthält.

Have fun!

Das könnte Dich auch interessieren:

Kommentare

  1. Wie viele Primzahlen kannst Du denn mit dem Sieb finden? Alle Primzahlen bis 1.000.000.000.000 finden sich auf primzahlen.zeta24.com.

  2. Also in erster Linie geht’s ja nur um die Funktion array_walk … allerdings interessieren mich grundsätzlich solche Dinge (sie faszinieren mich), sodass ich solche Beispiele gern benutze, um von diesem üblichen Code-Beispielen wegzukommen.

Deine Meinung ist uns wichtig

*