Eratostenovo sito
Z Wikipédie
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).
[úprava] 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.
