Sieb des Eratosthenes
wuerg, 26.02.2022 22:00
Man kann mit den Zahlen 2, 3, 4, 5, ... beginnend schrittweise zusammengesetzte aus dieser Liste wie folgt entfernen (aussieben): Ist vor dem n‑ten Schritt pₙ die n‑te noch (im Sieb) verbliebene Zahl (O), so werden die echten Vielfachen von pₙ entfernt (X), fallen durch das Sieb. Letztlich bleiben nur die Primzahlen pₙ übrig. Bis 73 sieht das wie folgt aus:
Diese Methode heißt Sieb des Eratosthenes, obwohl er es allenfalls in seiner Bibliothek neben dem Erdumfang gefunden haben wird. Sicherlich hat er die 1 vorne nicht ausgelassen und in ihr eine Primzahl gesehen. [1] Soweit es eine Urform gab, wurden möglicherweise im n-ten Schritt auch einfach die echten Vielfachen von n+1 herausgesiebt, was langsamer zum gleichen Ergebnis führt.
[1] The On-Line Encyclopedia of Integer Sequences. Nichtzusammengesetzte Zahlen A008578. Bis vor hundert Jahren sah man in der 1 noch eine Primzahl, heute ist sie weder prim noch zusammengesetzt, sondern Einheit.
37 | 73 | Sieb von Josephus | Primzahlen
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 Vielfachen 4, 6, 8, 10, … entfernt (X) werden. Für den zweiten Schritt (n=2) ist pₙ=3 die zweite ungestrichene Zahl. Entfernt (X) werden nur 9, 15, 21, 27, …, da 6, 12, 18, 24, … bereits fehlen. Es folgt die dritte Siebung mit p₃=5, in der 25, 35, 55, 65 durchfallen. Um alle 21 Primzahlen bis 73 zu finden, reicht ein vierter Durchgang mit p₄=7 samt Verlust der 49, denn jede Siebung n entfernt als kleinste Zahl das Quadrat von pₙ, was für n>4 die 73 übersteigt.Diese Methode heißt Sieb des Eratosthenes, obwohl er es allenfalls in seiner Bibliothek neben dem Erdumfang gefunden haben wird. Sicherlich hat er die 1 vorne nicht ausgelassen und in ihr eine Primzahl gesehen. [1] Soweit es eine Urform gab, wurden möglicherweise im n-ten Schritt auch einfach die echten Vielfachen von n+1 herausgesiebt, was langsamer zum gleichen Ergebnis führt.
[1] The On-Line Encyclopedia of Integer Sequences. Nichtzusammengesetzte Zahlen A008578. Bis vor hundert Jahren sah man in der 1 noch eine Primzahl, heute ist sie weder prim noch zusammengesetzt, sondern Einheit.
37 | 73 | Sieb von Josephus | Primzahlen
... comment
