Theorie:
Eine einfache, und auf das antike Griechenland zurückgehende Methode, Primzahlen zu bestimmen, ist das Sieb des Eratosthenes. Die grundlegende Idee dabei ist folgende: Ist \(p\) eine Primzahl, so werden alle Vielfache davon keine Primzahlen mehr sein (weil ja \(p\) immer ein nichttrivialer Teiler ist). Um mit dem Sieb des Eratosthenes Primzahlen zu finden, kann man wie folgt vorgehen:
- Um alle Primzahlen kleiner gleich \(n\) zu finden, schreibe eine Liste der natürlichen Zahlen größer gleich \(2\) und kleiner gleich \(n\). Wir illustrieren das hier am Beispiel \(n=20\):
\((2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)\) - Die erste Zahl in der Liste ist eine Primzahl. Wir markieren sie, und streichen alle Vielfachen davon aus der Liste:
\(( \underline{2}, 3, \not \!4,5,\not \!6,7,\not \!8,9,\not \!10,11,\not \!12,13,\not \!14,15,\not \!16,17,\not \!18,19,\not \!20)\)
Die durchgestrichenen Zahlen scheiden aus, sie werden keine Primzahlen sein. - Die nächste, nicht-durchgestrichene Zahl in der Liste ist \(3\). \(3\) ist also prim, und wir können alle Vielfachen streichen (wir brauchen dazu nicht die Vielfachen ausrechnen, sondern streichen einfach jede dritte Zahl in der Liste. Ist eine Zahl bereits durchgestrichen, bleibt sie durchgestrichen:
\(( \underline{2}, \underline{3}, \not \!4,5,\not \!6,7,\not \!8,\not \!9,\not \!10,11,\not \!12,13,\not \!14,\not \!15,\not \!16,17,\not \!18,19,\not \!20)\). - Die nächste Zahl in der Liste, die noch nicht durchgestrichen ist, ist \(5\), das ist also die nächste Primzahl - wir markieren sie, und streichen alle Vielfachen durch (in diesem Fall sind schon alle durchgestrichen:
\(( \underline{2}, \underline{3}, \not \!4,\underline 5,\not \!6,7,\not \!8,\not \!9,\not \!10,11,\not \!12,13,\not \!14,\not \!15,\not \!16,17,\not \!18,19,\not \!20)\).
- Tatsächlich sind wir auch schon fertig, weil \(5\cdot 5>20\). Zum Beispiel sind die Vielfachen von \(7\) alle schon gestrichen: \(2\cdot 7\) ist als Vielfaches von \(2\) weg, und \(3\cdot 7\) wäre als Vielfaches von \(3\) auch schon weg, und ist außerdem schon über \(20\).
- Alle noch nicht durchgestrichenen Zahlen sind Primzahlen: \(2,3,5,7,11,13,17,19\).
Wichtig!
Abbruch des Primzahlsiebes: Sobald man bei einer Primzahl \(p\) angekommen ist, für die \(p\cdot p>n\) gilt, kann man den Vorgang abbrechen, und alle noch nicht durchgestrichenen Zahlen sind Primzahlen.
Weitere Erklärungen finden sich auch in Wikipedia.