Sieb des Eratosthenes
In diesem Kapitel schauen wir uns an, was das Sieb des Eratosthenes ist.
Erforderliches Vorwissen
- Was ist eine Primzahl?
Definition
Seit Jahrtausenden suchen Mathematiker nach einer Formel zur Berechnung der Primzahlen. Bislang verlief die Suche erfolglos, was nicht heißen soll, dass nicht doch mal irgendwann eine solche Formel entdeckt wird. Bis es soweit ist, können wir unseren Hunger nach Primzahlen durch das Sieb des Eratosthenes (etwa 276 bis 194 v. Chr.) stillen.
Das Sieb des Eratosthenes ist ein Verfahren zur Bestimmung von Primzahlen.
Beispiel
Anhand eines Beispiels zeige ich euch, wie das Verfahren funktioniert:
Alle Zahlen von $\boldsymbol{1}$ bis $\boldsymbol{N}$ aufschreiben
$N$ steht für eine beliebige natürliche Zahl. Es handelt sich dabei um die sog. obere Schranke.
In unserem Beispiel wählen wir $N = 100$.
$1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
$11$ | $12$ | $13$ | $14$ | $15$ | $16$ | $17$ | $18$ | $19$ | $20$ |
$21$ | $22$ | $23$ | $24$ | $25$ | $26$ | $27$ | $28$ | $29$ | $30$ |
$31$ | $32$ | $33$ | $34$ | $35$ | $36$ | $37$ | $38$ | $39$ | $40$ |
$41$ | $42$ | $43$ | $44$ | $45$ | $46$ | $47$ | $48$ | $49$ | $50$ |
$51$ | $52$ | $53$ | $54$ | $55$ | $56$ | $57$ | $58$ | $59$ | $60$ |
$61$ | $62$ | $63$ | $64$ | $65$ | $66$ | $67$ | $68$ | $69$ | $70$ |
$71$ | $72$ | $73$ | $74$ | $75$ | $76$ | $77$ | $78$ | $79$ | $80$ |
$81$ | $82$ | $83$ | $84$ | $85$ | $86$ | $87$ | $88$ | $89$ | $90$ |
$91$ | $92$ | $93$ | $94$ | $95$ | $96$ | $97$ | $98$ | $99$ | $100$ |
$\boldsymbol{1}$ streichen, denn $\boldsymbol{1}$ ist keine Primzahl
$\cancel{1}$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
$11$ | $12$ | $13$ | $14$ | $15$ | $16$ | $17$ | $18$ | $19$ | $20$ |
$21$ | $22$ | $23$ | $24$ | $25$ | $26$ | $27$ | $28$ | $29$ | $30$ |
$31$ | $32$ | $33$ | $34$ | $35$ | $36$ | $37$ | $38$ | $39$ | $40$ |
$41$ | $42$ | $43$ | $44$ | $45$ | $46$ | $47$ | $48$ | $49$ | $50$ |
$51$ | $52$ | $53$ | $54$ | $55$ | $56$ | $57$ | $58$ | $59$ | $60$ |
$61$ | $62$ | $63$ | $64$ | $65$ | $66$ | $67$ | $68$ | $69$ | $70$ |
$71$ | $72$ | $73$ | $74$ | $75$ | $76$ | $77$ | $78$ | $79$ | $80$ |
$81$ | $82$ | $83$ | $84$ | $85$ | $86$ | $87$ | $88$ | $89$ | $90$ |
$91$ | $92$ | $93$ | $94$ | $95$ | $96$ | $97$ | $98$ | $99$ | $100$ |
Ab dem nächsten Schritt läuft das Verfahren immer gleich ab:
Wir markieren die nächste nicht durchgestrichene Zahl $n$ und streichen jede $n$-te Zahl.
Wenn das Quadrat (also $n^2$) der nächsten nicht durchgestrichenen Zahl größer ist als die obere Schranke $N$, sind wir am Ende. Jede nicht durchgestrichene Zahl ist dann eine Primzahl.
$\boldsymbol{2}$ markieren und alle Vielfachen von $\boldsymbol{2}$ streichen
$\cancel{1}$ | ${\color{green}2}$ | $3$ | ${\color{red}\cancel{4}}$ | $5$ | ${\color{red}\cancel{6}}$ | $7$ | ${\color{red}\cancel{8}}$ | $9$ | ${\color{red}\cancel{10}}$ |
$11$ | ${\color{red}\cancel{12}}$ | $13$ | ${\color{red}\cancel{14}}$ | $15$ | ${\color{red}\cancel{16}}$ | $17$ | ${\color{red}\cancel{18}}$ | $19$ | ${\color{red}\cancel{20}}$ |
$21$ | ${\color{red}\cancel{22}}$ | $23$ | ${\color{red}\cancel{24}}$ | $25$ | ${\color{red}\cancel{26}}$ | $27$ | ${\color{red}\cancel{28}}$ | $29$ | ${\color{red}\cancel{30}}$ |
$31$ | ${\color{red}\cancel{32}}$ | $33$ | ${\color{red}\cancel{34}}$ | $35$ | ${\color{red}\cancel{36}}$ | $37$ | ${\color{red}\cancel{38}}$ | $39$ | ${\color{red}\cancel{40}}$ |
$41$ | ${\color{red}\cancel{42}}$ | $43$ | ${\color{red}\cancel{44}}$ | $45$ | ${\color{red}\cancel{46}}$ | $47$ | ${\color{red}\cancel{48}}$ | $49$ | ${\color{red}\cancel{50}}$ |
$51$ | ${\color{red}\cancel{52}}$ | $53$ | ${\color{red}\cancel{54}}$ | $55$ | ${\color{red}\cancel{56}}$ | $57$ | ${\color{red}\cancel{58}}$ | $59$ | ${\color{red}\cancel{60}}$ |
$61$ | ${\color{red}\cancel{62}}$ | $63$ | ${\color{red}\cancel{64}}$ | $65$ | ${\color{red}\cancel{66}}$ | $67$ | ${\color{red}\cancel{68}}$ | $69$ | ${\color{red}\cancel{70}}$ |
$71$ | ${\color{red}\cancel{72}}$ | $73$ | ${\color{red}\cancel{74}}$ | $75$ | ${\color{red}\cancel{76}}$ | $77$ | ${\color{red}\cancel{78}}$ | $79$ | ${\color{red}\cancel{80}}$ |
$81$ | ${\color{red}\cancel{82}}$ | $83$ | ${\color{red}\cancel{84}}$ | $85$ | ${\color{red}\cancel{86}}$ | $87$ | ${\color{red}\cancel{88}}$ | $89$ | ${\color{red}\cancel{90}}$ |
$91$ | ${\color{red}\cancel{92}}$ | $93$ | ${\color{red}\cancel{94}}$ | $95$ | ${\color{red}\cancel{96}}$ | $97$ | ${\color{red}\cancel{98}}$ | $99$ | ${\color{red}\cancel{100}}$ |
$\boldsymbol{3}$ markieren und alle Vielfachen von $\boldsymbol{3}$ streichen
Manche Vielfache von $3$ sind bereits durchgestrichen. Praktisch, oder?
$\cancel{1}$ | ${\color{green}2}$ | ${\color{green}3}$ | $\cancel{4}$ | $5$ | $\cancel{6}$ | $7$ | $\cancel{8}$ | ${\color{red}\cancel{9}}$ | $\cancel{10}$ |
$11$ | $\cancel{12}$ | $13$ | $\cancel{14}$ | ${\color{red}\cancel{15}}$ | $\cancel{16}$ | $17$ | $\cancel{18}$ | $19$ | $\cancel{20}$ |
${\color{red}\cancel{21}}$ | $\cancel{22}$ | $23$ | $\cancel{24}$ | $25$ | $\cancel{26}$ | ${\color{red}\cancel{27}}$ | $\cancel{28}$ | $29$ | $\cancel{30}$ |
$31$ | $\cancel{32}$ | ${\color{red}\cancel{33}}$ | $\cancel{34}$ | $35$ | $\cancel{36}$ | $37$ | $\cancel{38}$ | ${\color{red}\cancel{39}}$ | $\cancel{40}$ |
$41$ | $\cancel{42}$ | $43$ | $\cancel{44}$ | ${\color{red}\cancel{45}}$ | $\cancel{46}$ | $47$ | $\cancel{48}$ | $49$ | $\cancel{50}$ |
${\color{red}\cancel{51}}$ | $\cancel{52}$ | $53$ | $\cancel{54}$ | $55$ | $\cancel{56}$ | ${\color{red}\cancel{57}}$ | $\cancel{58}$ | $59$ | $\cancel{60}$ |
$61$ | $\cancel{62}$ | ${\color{red}\cancel{63}}$ | $\cancel{64}$ | $65$ | $\cancel{66}$ | $67$ | $\cancel{68}$ | ${\color{red}\cancel{69}}$ | $\cancel{70}$ |
$71$ | $\cancel{72}$ | $73$ | $\cancel{74}$ | ${\color{red}\cancel{75}}$ | $\cancel{76}$ | $77$ | $\cancel{78}$ | $79$ | $\cancel{80}$ |
${\color{red}\cancel{81}}$ | $\cancel{82}$ | $83$ | $\cancel{84}$ | $85$ | $\cancel{86}$ | ${\color{red}\cancel{87}}$ | $\cancel{88}$ | $89$ | $\cancel{90}$ |
$91$ | $\cancel{92}$ | ${\color{red}\cancel{93}}$ | $\cancel{94}$ | $95$ | $\cancel{96}$ | $97$ | $\cancel{98}$ | ${\color{red}\cancel{99}}$ | $\cancel{100}$ |
$\boldsymbol{5}$ markieren und alle Vielfachen von $\boldsymbol{5}$ streichen
$\cancel{1}$ | ${\color{green}2}$ | ${\color{green}3}$ | $\cancel{4}$ | ${\color{green}5}$ | $\cancel{6}$ | $7$ | $\cancel{8}$ | $\cancel{9}$ | $\cancel{10}$ |
$11$ | $\cancel{12}$ | $13$ | $\cancel{14}$ | $\cancel{15}$ | $\cancel{16}$ | $17$ | $\cancel{18}$ | $19$ | $\cancel{20}$ |
$\cancel{21}$ | $\cancel{22}$ | $23$ | $\cancel{24}$ | ${\color{red}\cancel{25}}$ | $\cancel{26}$ | $\cancel{27}$ | $\cancel{28}$ | $29$ | $\cancel{30}$ |
$31$ | $\cancel{32}$ | $\cancel{33}$ | $\cancel{34}$ | ${\color{red}\cancel{35}}$ | $\cancel{36}$ | $37$ | $\cancel{38}$ | $\cancel{39}$ | $\cancel{40}$ |
$41$ | $\cancel{42}$ | $43$ | $\cancel{44}$ | $\cancel{45}$ | $\cancel{46}$ | $47$ | $\cancel{48}$ | $49$ | $\cancel{50}$ |
$\cancel{51}$ | $\cancel{52}$ | $53$ | $\cancel{54}$ | ${\color{red}\cancel{55}}$ | $\cancel{56}$ | $\cancel{57}$ | $\cancel{58}$ | $59$ | $\cancel{60}$ |
$61$ | $\cancel{62}$ | $\cancel{63}$ | $\cancel{64}$ | ${\color{red}\cancel{65}}$ | $\cancel{66}$ | $67$ | $\cancel{68}$ | $\cancel{69}$ | $\cancel{70}$ |
$71$ | $\cancel{72}$ | $73$ | $\cancel{74}$ | $\cancel{75}$ | $\cancel{76}$ | $77$ | $\cancel{78}$ | $79$ | $\cancel{80}$ |
$\cancel{81}$ | $\cancel{82}$ | $83$ | $\cancel{84}$ | ${\color{red}\cancel{85}}$ | $\cancel{86}$ | $\cancel{87}$ | $\cancel{88}$ | $89$ | $\cancel{90}$ |
$91$ | $\cancel{92}$ | $\cancel{93}$ | $\cancel{94}$ | ${\color{red}\cancel{95}}$ | $\cancel{96}$ | $97$ | $\cancel{98}$ | $\cancel{99}$ | $\cancel{100}$ |
$\boldsymbol{7}$ markieren und alle Vielfachen von $\boldsymbol{7}$ streichen
$\cancel{1}$ | ${\color{green}2}$ | ${\color{green}3}$ | $\cancel{4}$ | ${\color{green}5}$ | $\cancel{6}$ | ${\color{green}7}$ | $\cancel{8}$ | $\cancel{9}$ | $\cancel{10}$ |
$11$ | $\cancel{12}$ | $13$ | $\cancel{14}$ | $\cancel{15}$ | $\cancel{16}$ | $17$ | $\cancel{18}$ | $19$ | $\cancel{20}$ |
$\cancel{21}$ | $\cancel{22}$ | $23$ | $\cancel{24}$ | $\cancel{25}$ | $\cancel{26}$ | $\cancel{27}$ | $\cancel{28}$ | $29$ | $\cancel{30}$ |
$31$ | $\cancel{32}$ | $\cancel{33}$ | $\cancel{34}$ | $\cancel{35}$ | $\cancel{36}$ | $37$ | $\cancel{38}$ | $\cancel{39}$ | $\cancel{40}$ |
$41$ | $\cancel{42}$ | $43$ | $\cancel{44}$ | $\cancel{45}$ | $\cancel{46}$ | $47$ | $\cancel{48}$ | ${\color{red}\cancel{49}}$ | $\cancel{50}$ |
$\cancel{51}$ | $\cancel{52}$ | $53$ | $\cancel{54}$ | $\cancel{55}$ | $\cancel{56}$ | $\cancel{57}$ | $\cancel{58}$ | $59$ | $\cancel{60}$ |
$61$ | $\cancel{62}$ | $\cancel{63}$ | $\cancel{64}$ | $\cancel{65}$ | $\cancel{66}$ | $67$ | $\cancel{68}$ | $\cancel{69}$ | $\cancel{70}$ |
$71$ | $\cancel{72}$ | $73$ | $\cancel{74}$ | $\cancel{75}$ | $\cancel{76}$ | ${\color{red}\cancel{77}}$ | $\cancel{78}$ | $79$ | $\cancel{80}$ |
$\cancel{81}$ | $\cancel{82}$ | $83$ | $\cancel{84}$ | $\cancel{85}$ | $\cancel{86}$ | $\cancel{87}$ | $\cancel{88}$ | $89$ | $\cancel{90}$ |
${\color{red}\cancel{91}}$ | $\cancel{92}$ | $\cancel{93}$ | $\cancel{94}$ | $\cancel{95}$ | $\cancel{96}$ | $97$ | $\cancel{98}$ | $\cancel{99}$ | $\cancel{100}$ |
Die nächste nicht durchgestrichene Zahl ist $11$. Es gilt: $11^2 = 121$.
Da das Quadrat von $11$ größer ist als die obere Schranke ($N = 100$), sind wir am Ende.
Nicht vergessen: Jede nicht durchgestrichene Zahl ist eine Primzahl!
$\cancel{1}$ | ${\color{green}2}$ | ${\color{green}3}$ | $\cancel{4}$ | ${\color{green}5}$ | $\cancel{6}$ | ${\color{green}7}$ | $\cancel{8}$ | $\cancel{9}$ | $\cancel{10}$ |
${\color{green}11}$ | $\cancel{12}$ | ${\color{green}13}$ | $\cancel{14}$ | $\cancel{15}$ | $\cancel{16}$ | ${\color{green}17}$ | $\cancel{18}$ | ${\color{green}19}$ | $\cancel{20}$ |
$\cancel{21}$ | $\cancel{22}$ | ${\color{green}23}$ | $\cancel{24}$ | $\cancel{25}$ | $\cancel{26}$ | $\cancel{27}$ | $\cancel{28}$ | ${\color{green}29}$ | $\cancel{30}$ |
${\color{green}31}$ | $\cancel{32}$ | $\cancel{33}$ | $\cancel{34}$ | $\cancel{35}$ | $\cancel{36}$ | ${\color{green}37}$ | $\cancel{38}$ | $\cancel{39}$ | $\cancel{40}$ |
${\color{green}41}$ | $\cancel{42}$ | ${\color{green}43}$ | $\cancel{44}$ | $\cancel{45}$ | $\cancel{46}$ | ${\color{green}47}$ | $\cancel{48}$ | $\cancel{49}$ | $\cancel{50}$ |
$\cancel{51}$ | $\cancel{52}$ | ${\color{green}53}$ | $\cancel{54}$ | $\cancel{55}$ | $\cancel{56}$ | $\cancel{57}$ | $\cancel{58}$ | ${\color{green}59}$ | $\cancel{60}$ |
${\color{green}61}$ | $\cancel{62}$ | $\cancel{63}$ | $\cancel{64}$ | $\cancel{65}$ | $\cancel{66}$ | ${\color{green}67}$ | $\cancel{68}$ | $\cancel{69}$ | $\cancel{70}$ |
${\color{green}71}$ | $\cancel{72}$ | ${\color{green}73}$ | $\cancel{74}$ | $\cancel{75}$ | $\cancel{76}$ | $\cancel{77}$ | $\cancel{78}$ | ${\color{green}79}$ | $\cancel{80}$ |
$\cancel{81}$ | $\cancel{82}$ | ${\color{green}83}$ | $\cancel{84}$ | $\cancel{85}$ | $\cancel{86}$ | $\cancel{87}$ | $\cancel{88}$ | ${\color{green}89}$ | $\cancel{90}$ |
$\cancel{91}$ | $\cancel{92}$ | $\cancel{93}$ | $\cancel{94}$ | $\cancel{95}$ | $\cancel{96}$ | ${\color{green}97}$ | $\cancel{98}$ | $\cancel{99}$ | $\cancel{100}$ |
Anmerkung
Obwohl das Sieb des Eratosthenes schon Jahrtausende alt ist, können wir es auch heute noch einsetzen, um ohne Hilfe des Computers alle Primzahlen bis 100, alle Primzahlen bis 1000 oder alle Primzahlen bis 10000 (oder was auch immer) zu bestimmen. Zugegeben, wenn die obere Schranke sehr groß ist, wird das Verfahren ziemlich zeitaufwändig. Dann lieber doch mit dem Computer!
