Ein Algorithmus zur Primzahlenumeration

[Delphi-Laie]

Eine (einfache oder komplexere) Formel zur Erzeugung der Primzahlen, optimalerweise der x. Primzahl, soll es ja bis heute nicht geben. Wohl gibt es aber inzwischen von Gerald Bühler einen siebfreien (i.Ggs.z. Eratosthenes, Atkin) Algorithmus zur Generierung derselben, der allerdings mit einem Hiflsarray arbeitet und bei größeren Zahlen auch spürbar langsamer wird. Das geht aber vom algorithmischen Niveau her immer noch um Größenordnungen über die triviale und von der Laufzeit her inakzeptable Schulmethode heraus, über Probedivisionen aller ungeraden Zahlen (und ggf. Einbezug noch weiterer Teilbarkeitsregeln) bis hin zu den Wurzeln der Zahlen zu operieren und so die Primeigenschaft nach der Versuch-Und-Irrtum-Methode festzustellen.

Interessanterweise ist jener Algorithmus erweiterbar, wie ich hoffte, probierte und herausfand, sodaß man sich nicht vorher festlegen muß, bis zu welcher natürlichen Zahl n (oder alternativ bis zur Primzahl bis zur Nummer soundso) man enumerieren möchte (im Gegensatz zu den Sieben). Es sind also beliebig viele Primzahlen aufsteigend lückenlos generierbar bzw. enumerierbar.

Im Anhang befinden sich 3 Demonstrationsprogramme dazu, die ich auf die Schnelle erstellte. Primgen 1 ist das nach Delphi übersetzte Original, während Primgen 2 und 3 die nach oben offene Enumeration demonstrieren.

[Delphi-Laie]

Zurecht wurde im Delphi-Forum (bzw. in der Entwickler-Ecke) kritisiert, daß der Speicherverbrauch dieses hier vorgestellten Algorithmus' einem Eratoshenes-Sieb, das nur ungerade Zahlen speichert, gleicht.

Ich nahm mich der Sache an. Schon in der ersten Version fiel mir auf, daß das Hilfsarray überwiegend (in der weit überwiegend höheren und damit größeren "Hälfte") aus Nullen besteht. Tatsächlich wird es an falscher Stelle des Algorithmus' falsch dimensioniert, konret: natürlich überdimensioniert. Jetzt müßte es stimmen. Ich lud bei den drei Demonstrationsprogrammen die jeweils verbesserte Version hier hoch. Die obere Version ist also obsolet, leider kann ich den Beitrag oben nicht mehr editieren und mithin das dort löschen bzw. erneuern.

Viele Grüße

Delphi-Laie

Edit 1: Noch eine kleine Unsauberkeit korrigiert.

Edit 2: Nach dieser Korrektur wächst die Länge des Hilfsarrays anscheinend nur noch logarithmisch mit der Anzahl der ermittelten Primzahlen, fällt also bei wachsender Primzahlmenge bwz. wachsendem Primzahlarray immer weniger bis kaum noch ins Gewicht.