Řešení hlavolamu z FLOPu 34

Tentokrát bylo úkolem nalézt prvních sto prvočísel. Opět lze vymyslet několik různých algoritmů a já bych Vám tu chtěl předvést podle mého názoru nejrychlejší.

Každé číslo lze převést na součin dále nedělitelných čísel - prvočísel. Při zkoumání, zda je číslo prvočíslem (a je tudíž dělitelné jen jedničkou a sebou samým) postačí vyzkoušet již dříve nalezená prvočísla (proč zkoušet dělitelnost devíti, každé číslo dělitelné devíti je současně dělitelné třemi.

Dále není nutné zkoušet prvočísla větší než odmocnina ze zkoumaného čísla, protože výsledek dělení by byl menší než zkoumající číslo a pokud by byl celočíselný (tedy jednalo by se o prvočíslo), muselo by se to zjistit již dříve. Např. číslo 33 (odmocnina = 5.7446) je sice dělitelné 11, ale 33:11=3 a je tudíž vyhozeno jako neprvočíslo už při trojce.

Nakonec není samozřejmě nutné zkoumat sudá čísla, která jsou vždy dělitelná dvěma (což je jediné sudé prvočíslo).

Jasnější to bude možná při pohledu na vlastní program:

řádky:

10 - 80 Výpis hlavičky

90 Vynulování počítadla času

100 - 110 Dimenzace pole o 100 prvcích, kam se budou ukládat výsledky a nastavení prvních tří prvočísel, které nelze použitým algorimem zjistit plus jejich výpis na obrazovku

120 Nastavení proměnné CISLO na hodnotu 3, tedy třetí a zatím poslední prvočíslo

130 Cyklus odpočítávající c proměnné POCET zbývajících 97 počítanách prvočísel

140 Přičtení dvojky k poslednímu prvočíslu (aby bylo opět liché a zjištění jeho odmocniny.

150 Cyklus odpočítávající již známá prvočísla počínaje třetím (jedničku a dvojku vzhledem k podmínkám nemá cenu zkoušet)

160 Pokud je Q-té prvočíslo již větší než odmocnina ze zkoumaného čísla, jedná se rovněž o prvočíslo

170 Pokud ale je výsledek dělení CISLO/A(Q) celočíselné, o prvočíslo se určitě nejedná a dále se číslo nezkoumá

180 Konec zkoumacího cyklu

190 Číslo bylo shledáno prvočíslem, vypíše se a začne se vyhledávat další

200 Číslo není prvočíslem a POCET je nutné snížit o jednotku, neboť se na dalším řádku inkrementuje

210 Konec hlavního cyklu

220 - 270 Bylo nalezeno 100 prvočísel a vypíše se doba výpočtu