Erastothenovo síto
Algoritmus
Erastothenovo síto je algoritmus pro nalezení všech prvočísel až po zadanou horní mez (dále ji
budeme označovat jako N).
Algoritmus obecně pracuje tak, že:
 Nejdříve vytvoří seznam všech čísel od 2 po N.
 Poté opakuje do chvíle, než dojde k N:
o První číslo v seznamu označ za prvočíslo
o Odeber toto číslo ze seznamu
o Najdi v seznamu všechny jeho násobky a odeber je ze seznamu
Pro další informace se můžete podívat na http://cs.wikipedia.org/wiki/Eratosthenovo_s%C3%ADto.
Pro naše účely je nejlepší vytvořit si pole o velikosti N+1 a vložit do něj všechna čísla od 0 do N,
protože potom bude např. číslo 2 na pozici pole[2] atd. To nám výrazně usnadní práci, když
budeme v cyklech definovat, kde máme začít a kde skončit.
Vzhledem k tomu, že v C nemůžeme „odstranit“ číslo z pole, je nutné to řešit přepsáním dané buňky
na nějakou (vždy stejnou) hodnotu, kterou budeme dále v programu ignorovat (např. číslo 0).
Nejprve všechna prvočísla najděte (v poli vám zůstanou prvočísla na správných pozicích a jinak samé
nuly) a teprve poté (v dalším cyklu) je spočítejte a nalezněte nejvyšší.
Pozor! Číslo 1 není považováno za prvočíslo, zohledněte to při výpisu a při počítání prvočísel.
Požadavky
 Program nalezne všechna prvočísla do zadané hranice (celé kladné číslo – ověřte, že uživatel
zadal platnou hodnotu
 Program vypíše nalezená prvočísla na obrazovku
 Program vypíše nejvyšší nalezené prvočíslo
 Program vypíše počet nalezených prvočísel