Prvočíslo

Sestavte algoritmus pro zjištění, jestli zadané číslo je prvočíslo. Prvočíslo je celé číslo, které je dělitelné pouze 1 a samo sebou. Vstupem algoritmu tedy bude zadané číslo a výstupem algoritmu bude vypsání, jestli zadané číslo je, nebo není prvočíslo.

Metod na zjišťování je více. My si vystačíme s tou nejjednodušší, a to takovou, že projdeme všechna čísla od 1 do zadaného a vyzkoušíme, jestli některé z nich nedělí zadané . Všechna čísla od 1 do projdeme v cyklu. Abychom se po skončení cyklu mohli rozhodnout, jestli je dané číslo prvočíslo, nebo nikoliv, potřebujeme vědět, zda ho nějaké číslo dělí. Opět nebudeme vymýšlet nic složitého – počet čísel, která zadané číslo dělí, si spočítáme.

Abychom si ukázali, že cyklus nemusí být jen od 1 do , tak si provedeme malou optimalizaci. Každé číslo je dělitelné 1 a samo sebou, takže je jasné, že v rozmezí od 1 do bude zadané číslo dělit číslo 1 a číslo . Z tohoto důvodu je nemusíme vůbec zkoušet a rozmezí cyklu může být od 2 do (větší optimlizaci dosáhneme tím, že by cyklus byl od 2 do odmocniny z , což není ani zdaleka poslední možnost). Pokud nebudeme do počtu dělitelů započítávat 1 a sebe sama, tak prvočíslo bude takové číslo, které bude mít v rozmezí 2 až celkem nula dělitelů.

Test dělitelnosti provádíme výpočtem, tzv. zbytku po dělení (operace modulo). Pro zápis operace zbytku po dělení se používá příkaz % nebo mod, např. výpočet zbytku po dělení 3: nebo mod 3. My budeme používat první zápis se znakem procent, který je používanější a úspornější v zápisu (například: 7 % 3 = 1).

Ve výsledném vývojovém diagramu nejprve inicializujeme celkový počet dělitelů (proměnnou ) na 0 a načteme testované číslo od uživatele. Dále v cyklu projedeme všechna čísla od 2 do čísla, které je o jedno menší než zadané uživatelem. Těmito čísly z cyklu (index) zkusíme vydělit zadané číslo – zjistíme, jaký je zbytek po dělení. Pokud je zbytek nulový, pak je zadané číslo od uživatele dělitelné indexem a jediné, co provedeme, je přičtení 1 do proměnné , která obsahuje celkový počet dělitelů. Na konci cyklu vyhodnotíme proměnnou . Pokud je nulová, tak nebylo nalezeno žádné číslo, které by zadané dělilo, a proto je výsledkem vypsaný text, že zadané číslo je prvočíslo. V opačném případě, kdy hodnota není nulová, existovalo alespoň jedno číslo, které zadané číslo dělilo, a proto se nemůže jednat o prvočíslo.