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