Prvočísla

Z matematiky víme, že prvočíslo je přirozené číslo větší než 1, které je dělitelné beze zbytek jen jedničkou a samo sebou. Jednička tedy není prvočíslo, protože nemá dva dělitele. Prvním prvočíslem je číslo 2 (je jediným sudým prvočíslem). 

V hlavním programu bude od uživatele načten počet prvočísel v řadě, která mají být v konzole vypsána - viz Obrázek 1. Pokud uživatel zadá záporný počet, vypíšeme varovnou hlášku a budeme simulovat ukončení tohoto programu pomocí značky Breakpoint (značka osmiúhelníku). Tím bude běh programu pozastaven a nebudou se vykonávat následující příkazy. 

V cyklu s podmínkou na začátku budeme v řídící podmínce cyklu testovat, zda již byla vypsána všechna prvočísla v řadě. To znamená, jestli je počet vypsaných čísel menší než požadovaný počet, necháme probíhat cyklus, ve kterém budeme testovat pomocí podprogramu Prvocislo testovat (funkce s návratem typu boolean), zda předané číslo je prvočíslem. Tento podprogram předá zpět do hlavního programu informaci, zda předané číslo je prvočíslo (hodnota true), nebo nikoliv (hodnota false). Pokud je testované číslo prvočíslem, připojíme ho do řady čísel, která jsou od sebe oddělena čárkami. Tento textový řetězec číslic necháme vypsat v hlavním programu.

Obrázek 1: Hlavní program Prvocisla pro výpis řady prvočísel

V cyklu hlavního programu je volána funkce Prvocislo, která navrací informaci, zda předané číslo je prvočíslo, nebo nikoliv - viz Obrázek 2. V této funkci jsou deklarovány dvě lokální proměnné. První booleanovská proměnná b obsahuje informaci, zda předané číslo uložené ve formálním parametru n je prvočíslem. Ještě před proběhnutím cyklu testované číslo prohlásíme za prvočíslo (b = true) - inicializace. Do proměnné i budeme ukládat jednotlivé hodnoty, kterými budeme předané číslo dělit. Pro tento účel využijeme operaci pro zbytek po celočíselném dělení (pomocí operátoru %). Řídící podmínka cyklu se skládá ze dvou částí, které musí obě být zároveň splněny. První část podmínky b == true podmiňuje vstup do cyklu za předpokladu, že předané číslo je stále prvočíslem. Jak si můžeme všimnout, uvnitř těla cyklu je umístěn rozhodovací blok, ve kterém je testováno, zda zbytek po celočíselném dělení předaného čísla dělitelem (aktuálním číslem uloženém v čítači) je roven nule. Pokud je tato podmínka splněna, nejedná se o prvočíslo, protože předané číslo je beze zbytku dělitelné jedničkou, samo sebou, ale zároveň i dalším dělitelem uloženým v čítači i. Dělitel je před příchodem do další iterace inkrementován o hodnotu 1. 

Druhá část řídící podmínky cyklu je, že cyklus bude probíhat, pokud aktuální číslo bude menší než předané číslo (chceme otestovat všechny dělitele v rozsahu od 2 do n-1). 

 Obrázek 2: Podprogram Prvocislo - funkce pro testování, zda předané číslo je prvočíslem

V předchozím algoritmu jsme procházeli čísla od 2 do n-1. Tento algoritmus je vhodný pro malá čísla. Problém však nastává u větších čísel. Vypišme si například řadu čísel od 2 do 20:

Řada: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Pokud se nad touto řadou zamyslíme, vidíme, že prvním prvočíslem je číslo 2. Všechny jeho násobky již tedy nemohou být prvočísly, jelikož jsou už dělitelné číslem 2. Můžeme tedy škrtnout čísla, která jsou násobky 2 a tudíž nejsou prvočísly:

Prvočísla: 2

Řada: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Vidíme, že řada čísel již byla významně redukována. Stejným způsobem budeme pokračovat dalším prvočíslem 3 a jeho násobky škrtneme:

Prvočísla: 2, 3

Řada: 5, 7, 9, 11, 13, 15, 17, 19

A stejným postupem bychom pokračovali dalšími prvočísly, dokud nám zbývají další čísla v řadě. Jedná se o tzv. Eratosthenovo síto.

Dalším urychlením je, že nepotřebujeme procházet členy do 2 do n-1, ale postačí procházet pouze členy číselné řady, které budou splňovat podmínku $i< \sqrt[]{n}$.