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(n) die n‑te noch (im Sieb) verbliebene Zahl (O), so werden die echten Vielfachen von p(n) entfernt (X), fallen durch das Sieb. Letztlich bleiben nur die Primzahlen p(n) ü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(n) 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(n)=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(2)=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(3)=5, in der 25, 35, 55, 65 durchfallen. Um alle 21 Primzahlen bis 73 zu finden, reicht ein vierter Durchgang mit p(4)=7 samt Verlust der 49, denn jede Siebung n entfernt als kleinste Zahl das Quadrat von p(n), 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
