Nejpřirozenější způsob hledání prvočísel do zadaného maxima je vzít postupně každé číslo a zkoušet ho postupně dělit všemi čísly až do odmocniny z daného čísla.
Eratosthenovo síto je jednoduchý a mnohem rychlejší algoritmus k vyřešení stejné úlohy. Je pojmenován po řeckém matematikovi Eratosthenovi z Kyrény. Napíšeme si nejprve všechna čísla až do zadaného maxima. Pak si vezmeme první prvočíslo, tj. 2 a vyškrtáme se seznamu všechny jeho násobky. Další číslo 3 je opět prvočíslo, a tak ze zbylého seznamu vyškrtáme opět všechny jeho násobky. Číslo 4 už v seznamu není, protože je násobkem čísla 2. Pokračujeme tedy s číslem 5, které je opět prvočíslem ... To co nám ze seznamu zbyde po vyškrtání násobků jsou prvočísla do zadaného maxima.
Eratosthenovo síto je jednoduchý a mnohem rychlejší algoritmus k vyřešení stejné úlohy. Je pojmenován po řeckém matematikovi Eratosthenovi z Kyrény. Napíšeme si nejprve všechna čísla až do zadaného maxima. Pak si vezmeme první prvočíslo, tj. 2 a vyškrtáme se seznamu všechny jeho násobky. Další číslo 3 je opět prvočíslo, a tak ze zbylého seznamu vyškrtáme opět všechny jeho násobky. Číslo 4 už v seznamu není, protože je násobkem čísla 2. Pokračujeme tedy s číslem 5, které je opět prvočíslem ... To co nám ze seznamu zbyde po vyškrtání násobků jsou prvočísla do zadaného maxima.
| max |
Normální výpočetVýsledky
|
Eratosthenovo sítoVýsledky
|
(asi 275 př. n. l. Kyréna – 194 př. n. l. Alexandrie)
Eratosthenés z Kyrény byl matematik, astronom a zřejmě největší geograf antického Řecka. Působil též jako správce alexandrijské knihovny. Věnoval se také literární činnosti jako básník.