Sieb des Eratosthenes in Python

Das Sieb des Eratosthenes ist ein sehr verbreiteter Algorithmus, um die Primzahlen unterhalb einer gegebenen Zahl zu erhalten. Diese Zahl soll unter zehn Millionen liegen.

Der Algorithmus ist einfach zu verstehen und wird häufig in der Programmierung implementiert. Dieses Tutorial demonstriert die Implementierung des Sieve of Eratosthenes-Algorithmus von Python.

Beginnen wir damit, zunächst die Logik hinter diesem Algorithmus zu verstehen. Zuerst schreiben wir alle Zahlen zwischen 2 und der vorgegebenen Zahl Nehmen wir 50 an.

Dann nehmen wir die erste Primzahl 2 und markieren alle Zahlen, die grösser als ihr Quadrat und durch 2 teilbar sind. Das Gleiche wiederholen wir dann mit der nächsten Primzahl 3.

Das gleiche Verfahren wird durchgeführt, bis die Primzahl 7 Quadrat der nächsten Zahl nach 7 ist 121 und größer als 50. Nach Markierung aller Zahlen sind die nicht markierten Werte die Primzahlen bis 50.

Die folgende Abbildung zeigt das Endergebnis.

Verwendung von das Sieb des Eratosthenes in Python

Wir erstellen zunächst eine Liste des erforderlichen Bereichs. Diese Liste markiert den angegebenen Index mit True oder False.

Anfangs enthält die Liste alle Elemente als True. Wir werden eine verschachtelte Schleife verwenden, um die Änderungen vorzunehmen und Nicht-Prime-Positionen als False zu markieren.

Danach speichern wir die Positionen, an denen der Wert noch True ist, in einer neuen Liste. Diese Liste enthält die Primzahlen.

def sieve_of_eratosthenes(val):
    max = val + 1
    lst = [True] * max
    for i in range(2, int(val ** 0.5 + 1)):
        if lst[i]:
            for j in range(i * i, max, i):
                lst[j] = False
    final = []
    for i in range(2, max):
        if lst[i]:
            final.append(i)
    return final


print(sieve_of_eratosthenes(100))

Ausgabe:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Es ist möglich, geringfügige Änderungen am obigen Code vorzunehmen, um die Zeitkomplexität zu verbessern. Zum Beispiel können wir Mengen oder Wörterbücher verwenden, um Nicht-Primzahlen zu filtern.

Das Endergebnis wird in einer Liste zurückgegeben, aber verwenden Sie Wörterbücher oder Sätze, während Sie die Primzahlen und Nicht-Primzahlen als True oder False markieren.

def sieveoferatosthenes_dict(n):
    max = n + 1
    d = dict()
    for i in range(2, max):
        d[i] = True

    for i in d:
        factors = range(i, max, i)
        for f in factors[1:]:
            d[f] = False
    lst = [i for i in d if d[i] == True]
    return lst


print(sieveoferatosthenes_dict(100))

Ausgabe:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Im obigen Beispiel verwenden wir das Wörterbuch d zum Markieren der Werte als True oder False, um die Primzahlen herauszufiltern. Das Endergebnis befindet sich in einer Liste.