Sieb des Eratosthenes
Listen Sie alle Primzahlen bis N in nahezu linearer Zeit auf
Sieb des Eratosthenes ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Primzahlen in großer Menge
Manchmal benötigen Sie jede Primzahl bis N und nicht nur eine einzelne Prüfung. Das Sieb des Eratosthenes findet sie alle in einem Durchlauf. 🧹
Die zentrale Idee
Gehen Sie zunächst davon aus, dass jede Zahl prim ist. Streichen Sie dann die Vielfachen jeder gefundenen Primzahl, sodass nur echte Primzahlen übrig bleiben.
Die Markierungen einrichten
Erstellen Sie eine boolesche Liste, in der der Index i angibt, ob i prim ist. Dieses Array ist die Grundlage, auf der das Sieb arbeitet.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseDie Kandidaten durchlaufen
Gehen Sie i aufsteigend durch. Wenn Sie zum ersten Mal eine Zahl erreichen, die noch mit True markiert ist, muss sie eine neue Primzahl ohne kleineren Faktor sein.
Vielfache streichen
Markieren Sie für jede Primzahl i die Werte 2i, 3i, 4i und so weiter als nicht prim. Diese Vielfachen haben i offensichtlich als Teiler.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseBei i zum Quadrat beginnen
Beginnen Sie mit dem Streichen bei i*i statt bei 2i. Jedes kleinere Vielfache wurde bereits von einer früheren Primzahl entfernt, Sie können es daher überspringen.
Bei der Wurzel stoppen
Sie müssen das Sieb nur ausführen, solange i*i höchstens N ist. Nach der Quadratwurzel ist jede noch mit True markierte Zahl bereits prim.
Das vollständige Sieb
Kombinieren Sie den äußeren Durchlauf mit dem inneren Streichen. Nach der Schleife ist jeder Index, der noch mit True markiert ist, eine bestätigte Primzahl.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseDie Primzahlen sammeln
Übertragen Sie die fertigen Markierungen mit einer Comprehension in eine Liste. Nun verfügen Sie über jede Primzahl bis N und können schnelle Abfragen durchführen.
primes = [i for i, p in enumerate(is_prime) if p]Warum es schnell ist
Das Sieb läuft in ungefähr O(n log log n)-Zeit, also nahezu linear. Deshalb ist es bei wiederholten Einzelprüfungen deutlich überlegen.
Achten Sie auf den Speicher
Das Markierungsarray benötigt Speicher proportional zu N. Prüfen Sie bei sehr großen Grenzen Ihr Speicherbudget, bevor Sie es anlegen.
Schnelltest
Rufen Sie sich die kleine Optimierung in der inneren Schleife ins Gedächtnis.
Zusammenfassung
Sie können jetzt ein Sieb erstellen, das alle Primzahlen bis N in nahezu linearer Zeit auflistet, bei jeder Primzahl mit i*i beginnt und bei der Quadratwurzel stoppt. ✅
Häufig gestellte Fragen
Ist die Lektion „Sieb des Eratosthenes“ kostenlos?
Ja — der vollständige Text von „Sieb des Eratosthenes“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Sieb des Eratosthenes“?
Listen Sie alle Primzahlen bis N in nahezu linearer Zeit auf Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Sieb des Eratosthenes“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- GGT, KGV und der euklidische Algorithmus
- Primzahltest bis sqrt(n)
- Sieb des Eratosthenes
- Primfaktorzerlegung und Teiler