Zahlwort

Man kann mit den Zahlen 2, 3, 4, 5, ... beginnend schritt­weise zusam­menge­setz­te aus dieser Liste wie folgt ent­fernen (aus­sieben): Ist vor dem n‑ten Schritt pₙ die n‑te noch (im Sieb) ver­blie­bene Zahl (O), so werden die echten Vielfachen von pₙ ent­fernt (X), fallen durch das Sieb. Letzt­lich bleiben nur die Primzahlen pₙ übrig. Bis 73 sieht das wie folgt aus:

               1         2         3         4         5         6         7              
n pₙ 234567890123456789012345678901234567890123456789012345678901234567890123
1  2   O|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
2  3   |O | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X | |
3  5   || O |   | |   | |   | X   | |   X |   | |   | |   | X   | |   X |   | |
4  7   || | O   | |   | |   |     | |     |   | |   | X   |     | |     |   | |
       23 5 7  11 13 17 19  23   29 31   37  41 43 47    53    59 61   67  71 73

Zu Beginn (n=1) ist pₙ=2 die erste Zahl im Sieb (O), deren echte Viel­fachen 4, 6, 8, 10, … ent­fernt (X) werden. Für den zweiten Schritt (n=2) ist pₙ=3 die zweite unge­stri­chene Zahl. Ent­fernt (X) werden nur 9, 15, 21, 27, …, da 6, 12, 18, 24, … bereits feh­len. Es folgt die dritte Siebung mit p₃=5, in der 25, 35, 55, 65 durch­fallen. Um alle 21 Prim­zahlen bis 73 zu finden, reicht ein vierter Durch­gang mit p₄=7 samt Verlust der 49, denn jede Siebung n ent­fernt als kleinste Zahl das Quadrat von pₙ, was für n>4 die 73 über­steigt.

Diese Methode heißt Sieb des Eratosthenes, obwohl er es allen­falls in seiner Biblio­thek neben dem Erd­umfang gefun­den haben wird. Sicher­lich hat er die 1 vorne nicht ausge­lassen und in ihr eine Prim­zahl gesehen. [1] Soweit es eine Urform gab, wurden mög­licher­weise im n-ten Schritt auch einfach die echten Viel­fachen von n+1 heraus­gesiebt, was lang­samer zum glei­chen Ergebnis führt.

[1] The On-Line Encyclopedia of Integer Sequences. Nicht­zusammen­gesetzte Zahlen A008578. Bis vor hundert Jahren sah man in der 1 noch eine Primzahl, heute ist sie weder prim noch zusammen­gesetzt, sondern Einheit.

37 | 73 | Sieb von Josephus | Primzahlen