Eratosthenovo síto je metoda, kterou lze najít všechna prvočísla menší než námi zvolené přirozené číslo. Eratosthenes vymyslel postup, jak nalézt všechna prvočísla menší než zadané přirozené číslo. K vyhledávání prvočísel používal voskové tabulky, na kterých měl napsána všechna přirozená čísla počínaje číslem 2 a konče zvoleným. Nejmenší číslo v tabulce (číslo 2) ponechal a na místa jeho násobků vypálil horkou jehlou dírku. Následujícím číslem v tabulce bylo číslo 3. Toto číslo opět ponechal a odstranil všechny jeho násobky. Dalším nejmenším zbylým číslem bylo 5. Opět jeho násobky odstranil. Takto pokračoval, dokud nedospěl k poslednímu. Po skončení vyhledávání prvočísel vypadala vosková tabulka jako síto. Proto se tato metoda hledání prvočísel v dnešní době označuje názvem Eratosthenovo síto.
Postup:
- např. do tabulky napíšeme všechna přirozená čísla počínaje číslem 2 do námi zvolené horní
meze
- označíme nejmenší číslo - číslo 2 (prvočíslo) a jeho násobky odstraníme
- další zbylé nejmenší číslo (číslo 3) je opět prvočíslo a jeho násobky se odstraní
- následující neškrtnuté číslo je 5, prvočíslo, jehož násobky se odstraní
- tímto způsobem pokračujeme do doby, dokud za prvočíslo není označeno číslo větší než
druhá odmocnina námi zvolené horní meze
- následují zbylá (neškrtnutá) čísla jsou již všechna prvočísla
Je jistě patrné, že tato metoda je značně omezená a použitelná jen při relativně malých konečných číslech. Při zvolených číslech řádů tisíců a více je velice časově náročná a ručně téměř nepoužitelná. V dnešní době existuje spousta programů na vyhledávání prvočísel právě za pomocí tohoto algoritmu. Přesto i pomocí počítačů tímto algoritmem nenajdeme největší známé prvočíslo, protože takové megaprvočíslo má více jak 4 milióny cifer
Na tuto otázka nalezl odpověď Američan polského původu Stanislaw Marcin Ulam (1909-1984).
Ulam při jednom ze svých pokusů začal do polí nekonečné šachovnice zapisovat do spirály přirozená čísla. Posléze si všiml, že prvočísla tvoří jakési úhlopříčky. Tedy rozmístění prvočísel se řídí nějakou zákonitostí. Tato zákonitost ovšem nebyla zatím přesně popsána.
