Primzahlen in PHP

Eigentlich kann es ja nicht schwer sein, eine Primzahl zu erkennen, oder? Das erste was einem einfällt ist wohl der Sieb des Eratosthenes. Das wurde bereits vor tausenden von Jahren rausgefunden, ist einfach und schnell implementiert. Aber ob eine x-beliebige Zahl eine Primzahl ist, kann mit diesem Verfahren nicht optimal getestet werden. Teste einfach mal die 40000003 oder die 39999979… Zur Erstellung von Primzahlen-Tafeln kann man das Verfahren jedoch gut benutzen. Das Verfahren läuft so ab:

  • Alle Zahlen von 2 bis N in ein Array schreiben
  • Lösche für jede Zahl 2 ≤ k ≤ √N alle Nachfolger, die ein
    Vielfaches von k sind (unset)
  • Die verbleibenden Zahlen sind Primzahlen

Beispiel: k=2, also können wir alle Vielfachen 4,6,8,… streichen. Easy :-). Aber die Laufzeit ist leider exponentiell :-( und wir müssen alle Zahlen in einem Array speichern.

Das erste deterministisches Verfahren mit einer Laufzeit von O((log n)^12+e) bis O((log n)^3+e) ist der AKS-Primzahlentest (nachzulesen bei Google *g*). AKS steht für Agrawal, Kayal und Saxena, die Erfinder des Verfahrens. So und nun? Wie siehts mit einer Implementierung aus? … sagen wir mal… nicht so leicht. Aber vielleicht hat jemand bereits ein kleines PHP-Skript programmiert? Also her damit… klasse. Das spart mir seeeeeehr viel Zeit ;-)

Kommentar verfassen