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