V 15. kapitole
online kurzu vyššího programovacího jazyka C++ úrovně Elementary II najdete mezi zadáními praktických příkladů pro domácí procvičení i úlohu, ve které máte najít největší společný dělitel dvou čísel a také úlohu, ve které máte najít nejmenší společný násobek dvou čísel nebo jejich největší společný dělitel.
Sáhnete-li do osnov matematiky druhého stupně základní školy někde do 6. nebo 7. ročníku, zjistíte, že klíčem k vyřešení těchto dvou úkolů je rozklad obou čísel na součin prvočísel.
Úkoly patří z hlediska logiky a analytického myšlení mezi začátečnické. Přesto vím, že jsou náročnější. Právě proto jsem se rozhodl napsat tento blog.
V tomto blogu nechci řešit tento úkol za vás, ale alespoň bych vám rád podal návod, jak zjistit, zda je načtené číslo ze vstupu prvočíslem. Tento úkol je jeden z dílčích úkolů, které je třeba řešit při dvou zmíněných příkladech, jejichž řešení jste dostali za úkol najít.
Ti, kteří zapomněli, co je prvočíslo, ozřejmím i tento pojem. Prvočíslo je celé kladné číslo, které je dělitelné pouze jednotkou a svojí vlastní hodnotou. Budeme se tedy pohybovat pouze v množině kladných celých čísel. Příkladem prvočísla může být např. číslo 5, protože je dělitelné pouze číslem 1 a 5. dalšími příklady jsou 2, 3, 7, 11, 13, 17 atp. Samotné číslo 1 se za prvočíslo nepovažuje. Řekněme, že máme číslo 60, jeho rozklad na součin prvočísel je 2 x 2 x 3 x 5. Už z rozkladu je zřejmé, že jej můžeme vynásobit číslem 1, nic by to totiž nezměnilo na výsledku, pořád byste dostali číslo 60. Vidíte , a právě proto se matematici dohodli, že 1 prvočíslem nebude, nemá totiž již žádný vliv v součinu prvočísel, jehož výsledkem je nějaké číslo. Takže bez zbytečných dalších prázdných frází přejdu rovnou k věci. Následuje tedy zdrojový kód v jazyce C++, který řeší titulek tohoto blogu:
01: #include <iostream>
02: using namespace std;
03:
04: int main()
05: {
06: int iNumb;
07:
08: cout << "Zadaj lubovolne cele kladne cislo: ";
09: cin >> iNumb;
10: cout << endl;
11:
12: bool flag = true;
13:
14: if (iNumb == 1)
15: {
16: flag = false;
17: }
18: else
19: {
20: for (int i = 2; i <= iNumb / 2; i++)
21: {
22: if (iNumb % i == 0)
23: {
24: flag = false;
25: break;
26: }
27: }
28: }
29:
30: if (flag)
31: {
32: cout << "Cislo " << iNumb << " je prvocislo !" << endl;
33: }
34: else
35: {
36: cout << "Cislo " << iNumb << " nie je prvocislo !" << endl;
37: }
38:
39: cout << endl;
40:
41: cin.get();
42: cin.get();
43:
44: return 0;
45: }
Na řádku 01 je uvedena direktiva preprocesoru #include, jejímž parametrem je standardní knihovna iostream. Potřebujeme ji z důvodu používání objektů cout, cin a manipulátoru endl. Na řádku 02 uvádíme v platnost jmenný prostor std pro celý zdrojový soubor .cpp. Zmíněné objekty cout, cin a manipulátor endl je zároveň součástí tohoto prostoru. Na řádku 04 je uvedena funkce main i se svým návratovým typem, kterým je int (integer). Tuto funkci volá operační systém. Na řádku 05 je uvedena levá programová závorka, kterou začíná tělo funkce main. Na řádku 06 je deklarována proměnná iNumb pro datový typ int. Tato proměnná reprezentuje hodnotu celého kladného čísla, o kterém chceme zjistit, jestli patří mezi prvočísla. Na řádku 08 je pomocí objektu cout zapsán na výstup konzolové aplikace textový řetězec, který vyzve uživatele k zadání hodnoty kladného celého čísla, jehož vlastnost prvočísla testujeme. Na řádku 09 je prostřednictvím objektu cin načtena tato hodnota do proměnné iNumb. Na řádku 10 je prostřednictvím objektu cout a manipulátoru endl přesunut kurzor konzolové aplikace na další řádek. Na řádku 12 je deklarována proměnná flag a zároveň inicializována na hodnotu true. Tato proměnná nám bude po otestování načteného čísla ukládat informaci, zda je číslo prvočíslem nebo ne. Z hlediska logiky algoritmu je nutno proměnnou flag inicializovat před testováním na hodnotu true. Algoritmem budeme totiž testovat, zda načtené číslo mezi prvočísla nepatří. Používá se zde tedy postup vylučovací. Na řádku 14 je testována podmínka, zda v proměnné iNumb není hodnota 1. Pokud ano, program pokračuje kladnou větví a do proměnné flag se na řádku 16 zapíše hodnota false, která reprezentuje stav, kdy načtené číslo prvočíslem není. Na řádcích 13 a 15 jsou pouze uvedeny programové závorky, které uzavírají blok kódu uvedený v kladné větvi. Pokud zmíněná podmínka splněna není, pokračuje se zápornou větví. Blok kódu v záporné větvi uzavřen programovými závorkami na řádcích 19 a 29. Na řádcích 20 až 27 je uvedeno jádro algoritmu, který testuje vlastnost prvočísla u čísel větších než 1.
A v čem spočívá idea jádra algoritmu? V každé iteraci cyklu zjišťujeme, zda je číslo dělitelné hodnotou v proměnné i. Nejmenší číslo, kterým může být načteno testované dělitelné, je číslo 2 (viz. řádek 20 – for smyčka) a proto iterujeme od této hodnoty. Proměnnou i postupně inkrementujeme (viz. řádek 20 – for smyčka) a testujeme, zda je hodnota proměnné iNumb dělitelná beze zbytku pomocí operace modulo na řádku 22, která je umístěna v příkazu if. Pokud je číslo dělitelné hodnotou v proměnné i beze zbytku, tak se na řádku 24 uloží do proměnné flag hodnota false, což reprezentuje stav, kdy načtené číslo není prvočíslem. Proměnná i se inkrementuje po iNumb/2 (viz. řádek 20 – for smyčka). Důvodem je fakt, že žádné celé kladné číslo nemůže být přece dělitelné beze zbytku číslem větším než je jeho polovina.
Nenajde-li se tedy číslo, kterým je načtená hodnota testovaného čísla dělitelná beze zbytku, neuloží se do proměnné flag hodnota false, čili po ukončení v ní bude uložena hodnota true, což reprezentuje stav, kdy je načteno testované číslo prvočíslem. Na řádku 25 je uvedeno klíčové slovo break a to z toho důvodu, že v případě nalezení jednoho čísla, které dělí načtené testované číslo beze zbytku, není nutné hledat další dělitele. Testované číslo už prvočíslo totiž být nemůže a proto násilně ukončíme smyčku for, urychlíme program, který následně přejde až na řádek 30. Zde se už jen testuje hodnota v proměnné flag. Pokud je v této proměnné uložena hodnota true, tak se zapíše na výstup konzolové aplikace pomocí objektu cout informace o tom, že je načteno testované číslo prvočíslem (viz. řádek 32), pokud false tak informace, že prvočíslem není.
Na řádcích 41 a 42 je již jen načítán vstup z konzolové aplikace pomocí objektu cin, což slouží k tomu, aby se hned program neukončil a byl zobrazen výsledek v okně konzole, dokud uživatel nezatlačí libovolná klávesa. Na řádku 44 vrací funkce main operačnímu systému hodnotu 0, která indikuje stav správného ukončení aplikace. Na řádku 45 je ukončeno tělo programu pravou programovou závorkou. Algoritmus, který jsem navrhl a implementoval v jazyce C++, není ještě optimální. Je však pro účely kurzu úrovně začátečník dostačující. Mezi prvočísly lze ještě sledovat určité vlastnosti, nebudu je však tomto bloku vzpomínat, abych příliš posluchače úrovně začátečník zbytečně nadměrně nezatížil. Optimální algoritmus však budu ještě publikovat a rozebírat v dalším bloku a v kurzu, který bude zaměřen i na matematiku.
Skillmea
