Eratosthenovo síto
Algoritmus pro zjištění všech prvočísel, menších než horní mez / From Wikipedia, the free encyclopedia
Eratosthenovo síto je jednoduchý algoritmus pro nalezení všech prvočísel menších než zadaná horní mez. Je pojmenován po řeckém matematikovi Eratosthenovi z Kyrény, který žil v letech 276–194 př. n. l.
Algoritmus funguje „prosíváním“ seznamu čísel – na počátku seznam obsahuje všechna čísla v daném rozsahu (2, 3, 4, …, zadané maximum). Poté se opakovaně první číslo ze seznamu vyjme, toto číslo je prvočíslem; ze seznamu se pak odstraní všechny násobky tohoto čísla (což jsou čísla složená). Tak se pokračuje do doby, než je ze seznamu odstraněno poslední číslo (nebo ve chvíli, kdy je jako prvočíslo označeno číslo vyšší než odmocnina nejvyššího čísla – v takové chvíli už všechna zbývající čísla jsou nutně prvočísly). Časová složitost tohoto algoritmu je O(N*log(log N)), kde N je horní mez rozsahu.