Eratostenovo sito

Eratostenovo sito je jednoduchý algoritmus pre nájdenie všetkých prvočísel menších ako zadaná horná hranica. Algoritmus je pomenovaný po gréckom matematikovi Eratostenovi, ktorý žil v rokoch 276 – 194 pred Kr.

Algoritmus funguje na postupnom „presievaní“ zoznamu čísel – na začiatku zoznam obsahuje všetky čísla v danom rozsahu (2, 3, 4, …, zadané maximum). Potom sa opakovane prvé číslo zo zoznamu vyberie, toto číslo je prvočíslom; zo zoznamu sa potom odstránia všetky násobky tohto čísla (to sú zložené čísla). Tak sa pokračuje až dovtedy, kým sa zo zoznamu neodstráni posledné číslo (alebo dovtedy, keď je ako prvočíslo označené číslo vyššie ako odmocnina najvyššieho čísla – v tomto prípade všetky zostávajúce čísla v zozname sú určite prvočísla).

Príklad

Pre nájdenie prvočísel medzi prvými 20 číslami :

Krok 1: Zoznam obsahuje všetky čísla v rozsahu 2–20:

Zoznam: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Krok 2: Odoberieme prvé číslo zo zoznamu a označíme ho ako prvočíslo:

Známe prvočísla: 2

Zoznam: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Krok 3: Odoberieme zo zoznamu všetky násobky práve odobratého prvočísla:

Známe prvočísla: 2

Zoznam: 3 5 7 9 11 13 15 17 19

Krok 4: Pokračujeme opäť bodom 2, pokiaľ ostávajú nejaké čísla :

Známe prvočísla: 2 3

Zoznam: 5 7 11 13 17 19

Známe prvočísla: 2 3 5

Zoznam: 7 11 13 17 19

5 je vyšší než √19, takže ostávajú už iba prvočísla.

Výsledný zoznam prvočísel v rozsahu 2–20: 2, 3, 5, 7, 11, 13, 17, 19.

Príklad (Inak)

Ak máme vyhľadať napríklad všetky prvočísla menšie ako prirodzené číslo n = 30, napíšeme si (na papier) čísla od 2 do 30 (číslo 1 nie je prvočíslo!), zakrúžkujeme číslo 2 a vyškrtáme všetky jeho násobky. Potom zakrúžkujeme ďalšie najmenšie nevyškrtnúte číslo, čiže 3, a vyškrtáme všetky jeho násobky. To isté spravíme aj s číslami 5 a 7. Zakrúžkované čísla sú prvočísla.

Externé odkazy

• Interaktívna animácia Archivované 2001-03-01 na Wayback Machine (JavaScript)
• Eratostenovo sito