Sieb des Eratosthenes

Es ist möglich, alle Primzahlen kleiner als n wesentlich schneller zu finden, als jedes Mal einen Primzahltest für jede einzelne Zahl von 2 bis n durchzuführen. Statt jede Zahl auf ihre Primalität zu prüfen, können wir vorausschauend alle Zahlen aus der Liste entfernen, von denen wir sicher wissen, dass sie nicht prim sind.

Als Ausgangspunkt markieren wir alle Zahlen von 2 bis n als „möglicherweise prim“. Dann entfernen wir alle Vielfachen von 2 aus dieser Liste und markieren 2 als „definitiv prim“. Anschließend entfernen wir alle Vielfachen von 3 und markieren 3 als „definitiv prim“. Die 4 überspringen wir, da wir sie bereits als „nicht prim“ entfernt haben, als wir mit der 2 begonnen haben. Als Nächstes betrachten wir die 5 und entfernen auch deren Vielfache. Die 6 wird übersprungen, weil sie schon beim Durchlauf mit der 2 als nicht prim markiert wurde. So geht es weiter, bis wir n erreicht haben.

Simulation des Siebs des Eratosthenes. Klicken Sie auf die Zahlen und versuchen Sie, alle Primzahlen zu aktivieren, während Sie alle anderen deaktivieren.

Interessante Eigenschaften und Optimierungen des Algorithmus

Ein großer Vorteil des Vorgehens, bei dem wir ab der kleinsten Primzahl p alle Vielfachen von p aus der Liste möglicher Primzahlen entfernen und uns dann zur nächsten größeren Primzahl hocharbeiten, liegt darin, dass wir nicht bei 2·p, 3·p, 4·p usw. beginnen müssen, sondern direkt bei p·p. Da die Vielfachen von p wie 2·p, 3·p, 4·p, 5·p bereits entfernt wurden, als wir die Zahlen 2, 3, 5 … verarbeitet haben, ist p·p die erste Zahl, die noch nicht berücksichtigt wurde.

Wenn wir also bei p=3 anfangen, können wir gleich bei 9 beginnen, da 6 schon entfernt wurde, als wir die 2 verarbeitet haben. Genauso können wir bei p=5 direkt bei 25 starten, weil 10 (10 = 2·5) schon rausgefallen ist, als die 2 verarbeitet wurde, 15 (15 = 3·5) beseitigt wurde, als wir die 3 behandelt haben, und 20 (20 = 4·5) ebenfalls mit der 2 entfernt wurde.

prime = [True] * n                    # prime[i] = True => i ist eine Primzahl
prime[0] = prime[1] = False           # 0 und 1 sind keine Primzahlen

for i in range(2, n):                 # Schleife von 2 bis n
    if prime[i]:                      # wenn i prim ist => markiere alle Vielfachen von i als nicht prim
        for j in range(i * i, n, i):  # wir beginnen bei i * i, da alle kleineren Vielfachen von i bereits entfernt wurden
            prime[j] = False

Sieve of Eratosthenes to find all the prime numbers smaller than n.

Lassen Sie uns diesen Prozess für n=100 simulieren:

prime = [False, False, True, True, ..., True] der Größe 100

i = 2 ⇒ prime[2] = True ⇒ for j in 4, 6, 8, ... 100 und setzen prime[j]=False

i = 3 ⇒ prime[3] = True ⇒ for j in 9, 12, ... 100 und setzen prime[j]=False

i = 4 ⇒ prime[4] = False

i = 5 ⇒ prime[5] = True ⇒ for j in 25, 30, ... 100 und setzen prime[j]=False

i = 6 ⇒ prime[6] = False

i = 7 ⇒ prime[7] = True ⇒ for j in 49, 56, ... 100 und setzen prime[j]=False

i = 8 ⇒ prime[8] = False

i = 9 ⇒ prime[9] = False

i = 10 ⇒ prime[10] = False

i = 11 ⇒ prime[11] = True ⇒ for j in [empty] und setzen prime[j]=False

Hier können wir aufhören, da i * i bereits größer als n ist. Von diesem Punkt an werden keine weiteren Primzahlen als False markiert. Wir können also die Liste durchgehen und alle Primzahlen kleiner als 100 ausgeben.

Dieser Ansatz ist deutlich schneller und führt etwa Operationen aus. Das ist ein enormer Fortschritt! Statt -Operationen nur -Operationen durchzuführen, macht einen gewaltigen Unterschied aus. Wenn der Algorithmus, der für n Operationen etwa 10 Jahre (3650 Tage) brauchen würde und für -Operationen etwa 2 Monate (61 Tage), so wäre er bei -Operationen in weniger als 4 Tagen fertig!

Eine weitere Optimierung, die in der Simulation erwähnt wird, besteht darin, die äußere Schleife i nur bis laufen zu lassen, weil die innere Schleife bei i·i beginnt und für alle Zahlen größer als der Quadratwurzel von n keine weiteren Einträge mehr mit prime[j] = False markiert würden (die obere Grenze der inneren Schleife ist n).

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (2 ≤ n ≤ ).

Ausgabe

Das Programm soll alle Primzahlen ausgeben, die kleiner oder gleich n sind.

Beispiele

Input	Output
8	2 3 5 7
17	2 3 5 7 11 13 17
19	2 3 5 7 11 13 17 19

Interessante Eigenschaften und Optimierungen des Algorithmus

Eingabe

Ausgabe

Beispiele

Constraints

To check your solution you need to sign in

Sign in to continue