Eratostenovo sito
Ako možno nájsť všetky prvočísla menšie ako dané číslo? Návod nám dáva tzv. Eratostenovo sito. Vysvetlíme si jeho konštrukciu pre nájdenie všetkých prvočísel menších ako 200.
Najprv si všetky čísla 2 – 200 zapíšeme do tabuľky. (
Potom si označíme číslo 2 a sivou farbou podtieňujeme všetky jeho násobky. (
Následne si označíme číslo 3 a sivou farbou podtieňujeme všetky jeho násobky. (
Následne si označíme číslo 5 (lebo 4 je už podtieňované sivou) a sivou farbou podtieňujeme všetky jeho násobky. (
Následne si označíme číslo 7 (lebo 6 je už podtieňované sivou) a sivou farbou podtieňujeme všetky jeho násobky. (
Podobne si označíme čísla 11 a 13 a sivou farbou podtieňujeme všetky ich násobky. (
Pretože √200
14,14, násobky čísla 17 už sú podtieňované sivou všetky.
Všetky označené čísla spolu so všetkými nepodtieňovanými číslami sú prvočísla.
Zoznam prvočísel do 200: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.
Najprv si všetky čísla 2 – 200 zapíšeme do tabuľky. (
krok 1
)Potom si označíme číslo 2 a sivou farbou podtieňujeme všetky jeho násobky. (
krok 2
)Následne si označíme číslo 3 a sivou farbou podtieňujeme všetky jeho násobky. (
krok 3
)Následne si označíme číslo 5 (lebo 4 je už podtieňované sivou) a sivou farbou podtieňujeme všetky jeho násobky. (
krok 4
)Následne si označíme číslo 7 (lebo 6 je už podtieňované sivou) a sivou farbou podtieňujeme všetky jeho násobky. (
krok 5
)Podobne si označíme čísla 11 a 13 a sivou farbou podtieňujeme všetky ich násobky. (
krok 6
)Pretože √200
14,14, násobky čísla 17 už sú podtieňované sivou všetky.Všetky označené čísla spolu so všetkými nepodtieňovanými číslami sú prvočísla.
Zoznam prvočísel do 200: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.