Co je to Eratosthenovo síto?

Eratosthenovo síto - jednoduchý algoritmus, který hledá prvočísla v daném intervalu. Počítá s tím, že násobky prvočísel již nejsou prvočísla.

Seznam čísel tedy „prosívá“ dokud z něj není odstraněno poslední přebytečné číslo. Časová složitost tohoto algoritmu je (N*log(log N)), kde N je horní mez rozsahu. Algoritmus byl pojmenován po řeckém matematikovi Erastosthenovi z Kyrény.