V 15. kapitole
online kurzu vyššieho programovacieho jazyka C++ úrovne Elementary II nájdete medzi zadaniami praktických príkladov na domáce precvičenie aj úlohu, v ktorej máte nájsť najväčší spoločný deliteľ dvoch čísel a taktiež úlohu, v ktorej máte nájsť najmenší spoločný násobok dvoch čísel alebo ich najväčší spoločný deliteľ. Ak siahnete do osnov matematiky druhého stupňa základnej školy niekde do 6. alebo 7. ročníka, zistíte, že kľúčom k vyriešeniu týchto dvoch úloh je rozklad obidvoch čísel na súčin prvočísel.
Úlohy patria z hľadiska logiky a analytického myslenia medzi začiatočnícke. Napriek tomu viem, že sú náročnejšie. Práve preto som sa rozhodol napísať tento blog.
V tomto blogu nechcem riešiť túto úlohu za vás, ale aspoň by som vám rád podal návod, ako zistiť, či je načítané číslo zo vstupu prvočíslom. Táto úloha je jedna z čiastkových úloh, ktoré je potrebné riešiť pri dvoch spomenutých príkladoch, ktorých riešenie ste dostali za úlohu nájsť.
Tí, ktorí zabudli, čo je prvočíslo, ozrejmím aj tento pojem. Prvočíslo je celé kladné číslo, ktoré je deliteľné len jednotkou a svojou vlastnou hodnotou. Budeme sa teda pohybovať iba v množine kladných celých čísel. Príkladom prvočísla môže byť napr. číslo 5, pretože je deliteľné len číslom 1 a 5. ďalšími príkladmi sú 2, 3, 7, 11, 13, 17 atď. Samotné číslo 1 sa za prvočíslo nepovažuje. Povedzme, že máme číslo 60, jeho rozklad na súčin prvočísel je 2 x 2 x 3 x 5. Už z rozkladu je zrejmé, že ho môžeme vynásobiť číslom 1, nič by to totiž nezmenilo na výsledku, stále by ste dostali číslo 60. Vidíte, a práve preto sa matematici dohodli, že 1 prvočíslom nebude, nemá totiž už žiadny vplyv v súčine prvočísel, ktorého výsledkom je nejaké číslo. Takže bez zbytočných ďalších prázdnych fráz prejdem rovno k veci. Nasleduje teda zdrojový kód v jazyku C++, ktorý rieši titulok tohto 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 riadku 01 je uvedená direktíva preprocesora #include, ktorej parametrom je štandardná knižnica iostream. Potrebujeme ju z dôvodu používania objektov cout, cin a manipulátora endl. Na riadku 02 uvádzame do platnosti menný priestor std pre celý zdrojový súbor .cpp. Spomenuté objekty cout, cin a manipulátor endl je zároveň súčasťou tohto priestoru. Na riadku 04 je uvedená funkcia main aj so svojim návratovým typom, ktorým je int (integer). Túto funkciu volá operačný systém. Na riadku 05 je uvedená ľavá programová zátvorka, ktorou sa začína telo funkcie main. Na riadku 06 je deklarovaná premenná iNumb na údajový typ int. Táto premenná reprezentuje hodnotu celého kladného čísla, o ktorom chceme zistiť, či patrí medzi prvočísla. Na riadku 08 je pomocou objektu cout zapísaný na výstup konzolovej aplikácie textový reťazec, ktorý vyzve používateľa na zadanie hodnoty kladného celého čísla, ktorého vlastnosť prvočísla testujeme. Na riadku 09 je prostredníctvom objektu cin načítaná táto hodnota do premennej iNumb. Na riadku 10 je prostredníctvom objektu cout a manipulátora endl presunutý kurzor konzolovej aplikácie na ďalší riadok. Na riadku 12 je deklarovaná premenná flag a zároveň inicializovaná na hodnotu true. Táto premenná nám bude po otestovaní načítaného čísla ukladať informáciu, či je číslo prvočíslom alebo nie. Z hľadiska logiky algoritmu je nutné premennú flag inicializovať pred testovaním na hodnotu true. Algoritmom budeme totiž testovať, či načítané číslo medzi prvočísla nepatrí. Používa sa tu teda postup vylučovací. Na riadku 14 je testovaná podmienka, či v premennej iNumb nie je hodnota 1. Ak áno, program pokračuje kladnou vetvou a do premennej flag sa na riadku 16 zapíše hodnota false, ktorá reprezentuje stav, kedy načítané číslo prvočíslom nie je. Na riadku 13 a 15 sú len uvedené programové zátvorky, ktoré uzatvárajú blok kódu uvedený v kladnej vetve. Ak spomínaná podmienka splnená nie je, pokračuje sa zápornou vetvou. Blok kódu v zápornej vetve uzatvorený programovými zátvorkami na riadkoch 19 a 29. Na riadku 20 až 27 je uvedené jadro algoritmu, ktorý testuje vlastnosť prvočísla u čísel väčších ako 1.
A v čom spočíva idea jadra algoritmu ? V každej iterácii cyklu zisťujeme, či je číslo deliteľné hodnotou v premennej i. Najmenšie číslo, ktorým môže byť načítané testované deliteľné, je číslo 2 (viď. riadok 20 – for slučka) a preto iterujeme od tejto hodnoty. Premennú i postupne inkrementujeme (viď. riadok 20 – for slučka) a testujeme, či je hodnota premennej iNumb deliteľná bez zvyšku pomocou operácie modulo na riadku 22, ktorá je umiestnená v príkaze if. Ak je číslo deliteľné hodnotou v premennej i bez zvyšku, tak sa na riadku 24 uloží do premennej flag hodnota false, čo reprezentuje stav, kedy načítané číslo nie je prvočíslom. Premenná i sa inkrementuje po iNumb / 2 (viď. riadok 20 – for slučka). Dôvodom je fakt, že žiadne celé kladné číslo nemôže byť predsa deliteľné bez zvyšku číslom väčším ako je jeho polovica.
Ak sa teda nenájde číslo, ktorým je načítaná hodnota testovaného čísla deliteľná bez zvyšku, neuloží sa do premennej flag hodnota false, čiže po ukončení v nej bude uložená hodnota true, čo reprezentuje stav, kedy je načítané testované číslo prvočíslom. Na riadku 25 je uvedené kľúčové slovo break a to z toho dôvodu, že v prípade nájdenia jedného čísla, ktoré delí načítané testované číslo bez zvyšku, nie je nutné hľadať ďalšie delitele. Testované číslo už prvočíslo totiž byť nemôže a preto násilne ukončíme slučku for, urýchlime program, ktorý následne prejde až na riadok 30. Tu sa už len testuje hodnota v premennej flag. Ak je v tejto premennej uložená hodnota true, tak sa zapíše na výstup konzolovej aplikácie pomocou objektu cout informácia o tom, že je načítané testované číslo prvočíslom (viď. riadok 32), ak false tak informácia, že prvočíslom nie je.
Na riadku 41 a 42 je už len načítavaný vstup z konzolovej aplikácie pomocou objektu cin, čo slúži na to, aby sa hneď program neukončil a bol zobrazený výsledok v okne konzole, pokým používateľ nezatlačí ľubovoľná kláves. Na riadku 44 vracia funkcia main operačnému systému hodnotu 0, ktorá indikuje stav správneho ukončenia aplikácie. Na riadku 45 je ukončené telo programu pravou programovou zátvorkou. Algoritmus, ktorý som navrhol a implementoval v jazyku C++ nie je ešte optimálny. Je však pre účely kurzu úrovne začiatočník postačujúci. Medzi prvočíslami sa dajú ešte sledovať určité vlastnosti, nebudem ich však tomto bloku spomínať, aby som príliš poslucháča úrovne začiatočník zbytočne nadmerne nezaťažil. Optimálny algoritmus však budem ešte publikovať a rozoberať v ďalšom bloku a v kurze, ktorý bude zameraný aj na matematiku.
Skillmea
