Primzahlen

Ich habe das Sieb des Eratosthenes schon vor einiger Zeit mal programmiert.

(1) Ein Ansatz mit Listen und list comprehensions

Der Algorithmus wirkt in dieser Form bereits sehr schnell.

def sieben(zahl):
    ''' Eine erste Implementierung des
    Sieb des Eratosthenes mit Listen
    '''
    liste = [2]
    liste.extend([i for i in range(3,zahl+1,2)])
 
    for z in range(2,zahl+1):
        if z in liste:
            exliste = [e * z for e in range(z,zahl+1) if e * z <= zahl]
            # print(z, exliste)
            if len(exliste) == 0:
                break
            else:
                for e in exliste:
                    if e in liste:
                        liste.remove(e)
    return liste
 
 
ergebnis = sieben(10000)
 
print(", ".join(map(str,ergebnis)),end=".\n")

Das Skript nutzt str.join(iterable) und map. Das Skript macht sich zunutze, dass nur die ungeraden Zahlen geprüft werden müssen, weil alle geraden Zahlen außer 2 keine Primzahlen sind. Sobald die exliste leer ist, wird die Löschung abgebrochen, weil angenommen wird, dass alle weiteren Listen auch leer sein werden.

(2) Ein Ansatz mit einem Wörterbuch

Mit dem Wörterbuch wirkt der Algorithmus noch etwas schneller:

def sieben(zahl):
    ''' Eine erste Implementierung des
    Sieb des Eratosthenes mit einem Woerterbuch
    '''
    keys = [2]
    keys.extend([i for i in range(3,zahl,2)])

    woerterbuch = {}

    for key in keys:
        woerterbuch[key] = True  # True = prime (!)
          
    for key in keys:
        if woerterbuch[key] == True:
            vielfache = [i * key for i in range(key,zahl+1) if i * key <= zahl]
            # print(key,vielfache)
            if len(vielfache) == 0:
                break
            else:
                for item in vielfache:
                    if item in woerterbuch:
                        woerterbuch[item] = False
    return [i for i in keys if woerterbuch[i] == True]

ergebnis = sieben(1000)

print(", ".join(map(str,ergebnis)),end=".\n")

Gefühlt ist das auch für größere Zahlen sehr zügig. Ich verzichte hier auf eine mitlaufende Ausgabe, was sich leicht durch einen weiteren print-Befehl nach der Zeile

if woerterbuch[key] == True:

realisieren ließe. In diesem Fall könnte der Aufbau einer weiteren Liste und die return-Anweisung entfallen.

Performanz-Test

Mit dem Modul profiler - entsprechend den Hinweisen von Michael Weigend (4. Aufl.) 2010 - ergab sich folgendes Bild:

Ich hätte nicht erwartet, dass die Umsetzung mit dem Wörterbuch so viel performanter ist. Inzwischen habe ich weiter am Code geschraubt, so dass beide Skripte eigentlich noch etwas performanter geworden sein müssten. Das zweite Skript schafft die Prüfung des Zahlenraums bis 1.000.000 jetzt in ca. 38,34 Sekunden statt ursprünglich etwa 42,18 Sekunden.

Feedback aus dem Python-Forum

Hier der Link zum Thread. Offensichtlich gibt es bei beiden Implementierungen noch deutliches Optimierungspotential.