Was ist die effizienteste Methode, um Primzahlen zu berechnen?
Zur Berechnung von Primzahlen gibt es verschiedene Verfahren. Die drei bekanntesten sind wohl das Sieb des Eratosthenes, das Sieb von Atkin und das Sieb des Sundaram.
1. Sieb des Eratosthenes
Das Sieb des Eratosthenes ist nicht besonders komplex: Basis dafür ist eine Liste aller Zahlen von
2
bis
n
, wobei
n
die obere Grenze ist, bis zu der die Primzahlen bestimmt werden sollen. Zunächst wird jede Zahl als prim markiert. Dann werden nacheinander alle nicht gestrichenen Zahlen durchgegangen und deren Vielfachen gestrichen. Das ganze geht bis
n
−
−
√
und übrig bleibt eine Liste der Primzahlen von
2
bis
n
. So weit, so einfach.
from math import sqrt 
limit = 100 
primes = list(range(2, limit)) 
for i, el in enumerate(primes[:int(sqrt(limit)+1)]): 
    if el: # truthy value 
        for j in range(i + el, len(primes), el):  
            if primes[j]: 
          primes[j] = None # set every multiple to None 
 print([p for p in primes if p]) 
Laufzeitkomplexität:
O(nloglogn)
2. Sieb von Atkin[1][2]
Ein wenig komplizierter wird es mit dem Sieb von Atkin. Es ist eine optimierte Version des Sieb des Eratosthenes, indem am Anfang bestimmte modulo 12-Reste und am Ende alle Vielfachen von Primzahlquadraten gestrichen werden, sodass eine Liste von Primzahlen übrig bleibt. Zunächst initialisieren wir uns eine Siebliste mit einer bestimmten Anzahl
n
von Einträgen, von denen jede für eine natürliche Zahl steht. Außer
2
und
3
werden erst alle Zahlen als nicht-prim markiert.
limit = 100 
sieveList = [False, False, True, True, False] + [False] * (limit - 5) 
Jetzt wird schrittweise für jede Zahl
z
der Siebliste der Rest bei der Division durch
12
betrachtet. Wenn der Rest
1
oder
5
beträgt, ist die Zahl prim, wenn die Gleichung
4
x
2
+
y
2
=z
eine ungerade Anzahl an Lösungen besitzt (d. h., die Markierung wird für jede Lösung der Gleichung invertiert).
7
beträgt, ist die Zahl prim, wenn die Gleichung
3
x
2
+
y
2
=z
eine ungerade Anzahl an Lösungen besitzt.
11
beträgt, ist die Zahl prim, wenn die Gleichung
3
x
2
−
y
2
=z
mit
x>y
eine ungerade Anzahl an Lösungen besitzt.
x = 1 
while x * x < limit: # try each pair of x and y 
    y = 1 
    while y * y < limit: 
        z = 4*x*x + y*y 
        if z <= limit and (z % 12 == 1 or z % 12 == 5): 
            sieveList[z] ^= True 
         z = 3*x*x + y*y  
        if z <= limit and z % 12 == 7: 
            sieveList[z] ^= True 
         z = 3*x*x - y*y 
        if x > y and z <= limit and z % 12 == 11: 
            sieveList[z] ^= True 
         y += 1 
    x += 1 
Anschließend werden nacheinander bis
n
−
−
√
alle unmarkierten Elemente
r
durchgegangen (Primzahlen) und alle Vielfachen von
r
2
markiert.
r = 5 
while r * r < limit: 
    if sieveList[r]: 
        for i in range(r*r, limit, r*r):  
            sieveList[i] = False 
    r += 1 
Und das war's auch schon - jede unmarkierte Zahl (in unserem Fall jeder Eintrag True in der Liste) ist prim.
for prime in range(limit): 
    if sieveList[prime]: 
        print(prime) 
Laufzeitkomplexität:
O(n)
3. Sieb des Sundaram[3]
Ein sehr spannendes Sieb ist auch das Sieb des Sundaram. Mit einer oberen Grenze
n
muss zunächst eine Liste mit allen Zahlen von
1
bis
n
2
erstellt werden.
limit = 100 
nums = list(range(1, limit // 2)) 
Jetzt werden in dieser Liste alle Zahlen der Form
i+j+2ij
mit
i,j∈N
und
1≤i≤j
entfernt, solange
i+j+2ij≤n
.
j = 1 
i = 1 
current = i + j + 2*i*j 
while current <= limit: 
    for _ in range(j): # i <= j 
        if current > limit // 2 - 1: 
            break # result exceeds limit 
        nums[current - 1] = None 
        i += 1 
    j += 1 
    i = 1 
Übrig bleibt eine Liste mit Einträgen
r
, in der
2r+1
prim ist.
for r in range(limit // 2 - 1): 
    if nums[r]: # truthy value 
        print(nums[i]*2 + 1) 
Laufzeitkomplexität:
O(nlogn)
Das Sieb von Atkin ist mit der Ordnung
O(n)
also tatsächlich das effizienteste Verfahren.
Für mehr wie Primzahlgenerierung durch Radfaktorisierung und Myriad kann ich diese Arbeit von Juhani Sipiläs sehr empfehlen: [4]
Fußnoten
[1] http://fbmn.h-da.de/~tksprosem/uploads/Main/DamePraesentation.pdf
[2] Sieve of Atkin - GeeksforGeeks
[3] Sieve of Sundaram - Wikipedia
[4] https://pdfs.semanticscholar.org/ba51/12ec470de71a6f1574c41d483ac9393ad0d3.pdf