Sieb von Eratosthenes

1.4. Sieb von Eratosthenes#

Das Sieb von Eratosthenes ist ein Algorithmus, um alle Primzahlen bis zu einer gewissen Grenze zu finden. In dieser Aufgabe wird der Algorithmus bis zur Zahl 100 angewendet.

Aufgabenstellung#

Erstellen Sie sich eine Liste mit den Zahlen von 2 bis 100. Der Algorithmus geht nun wie folgt:

  • Nehmen Sie die kleinste, nicht markierte oder durchgestrichene Zahl

  • Markieren Sie diese Zahl als Primzahl

  • Streichen Sie alle Vielfachen dieser Zahl durch

  • Wiederholen Sie diese Schritte, bis alle Zahlen entweder markiert oder durchgestrichen sind

Aufgabenteil A#

Erstellen Sie eine Liste mit den Zahlen von 2 bis 100 und wenden Sie den Algorithmus auf diese Liste an

Lösungshinweise#

Die Primzahlen von 2 bis 100 sind:

[ 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]

Lösungsvorschlag#

Hide code cell outputs 
    2  3  x  5  x  7  x  x  x 
11  x 13  x  x  x 17  x 19  x 
 x  x 23  x  x  x  x  x 29  x 
31  x  x  x  x  x 37  x  x  x 
41  x 43  x  x  x 47  x  x  x 
 x  x 53  x  x  x  x  x 59  x 
61  x  x  x  x  x 67  x  x  x 
71  x 73  x  x  x  x  x 79  x 
 x  x 83  x  x  x  x  x 89  x 
 x  x  x  x  x  x 97  x  x  x

Aufgabenteil B#

Versuchen Sie die Komplexität des Algorithmus abzuschätzen und begründen Sie ihre Wahl

Lösungsvorschlag#

Das größte Problem beim Abschätzen der Komplexität ist, dass man nicht sagen kann, wie viele von n Zahlen tatsächlich Primzahlen sind. Was man jedoch sicher sagen kann ist, dass höchstens jede Zahl eine Primzahl ist. Mit dieser Abschätzung können wir den Algorithmus analysieren. Die simpelste Abschätzung der Komplexität wäre, dass wir für jede Primzahl schauen, ob jede andere Zahl durch sie teilbar ist. Bei n Zahlen ergibt sich eine Komplexität von

\(\mathcal{O}(n \cdot (n-1)) = \mathcal{O}(n^2).\)

Allerdings muss man nicht für jede der Zahlen jede andere überprüfen. Es reicht, wenn explizit die Vielfachen überprüft und gelöscht werden. Addiert man alle Überprüfungen zusammen, erhält man

\(\frac{n}{2} + \frac{n}{3} + \frac{n}{4} + … + \frac{n}{n}= n \cdot \sum_{i=2}^{n}\frac{1}{i}.\)

\(\sum_{i=1}^{n}\frac{1}{i}\) ist die Harmonische Reihe und divergiert mit \(\mathcal{O}(\ln(n))\). Dies erlaubt eine genauere Abschätzung zu

\(\mathcal{O}(n \cdot \mathcal{O}(\ln(n))) = \mathcal{O}(n \cdot \ln(n)).\)

Bonus: Der Algorithmus kann noch weiter optimiert werden, wenn man berücksichtigt, dass jede Zahl als Produkt von Primzahlen darstellbar ist. Nach den ersten \(\sqrt{n}\) Zahlen wurden alle Zahlen aus der Liste gestrichen, deren Primfaktorzerlegung mindestens eine der darin enthaltenen Primzahlen enthällt. Das bedeutet aber, dass die Primfaktorzerlegungen aller folgenden, nicht gestrichenen Zahlen nur aus Primzahlen größer als \(\sqrt{n}\) bestehen können. Da jedoch das Produkt von zwei dieser Zahlen immer größer als \(n\) ist, muss jede noch nicht gestrichene Zahl in der Liste eine Primzahl sein. Folglich kann der Algorithmus beendet werden, sobald die Vielfachen der Zahlen kleiner-gleich \(\sqrt{n}\) überprüft wurden. Für die Komplexität heißt dies:

\(\mathcal{O}(n \cdot \ln(\sqrt{n})).\)

Contents