Vzdelávanie
30.05.2020
Skillmea
Eratostenovo sito
V predchádzajúcom blogu sme sa zaoberali prvočíslami. Ukázali sme si ukážku programu, ktorý rozoznal, či zadané číslo je prvočíslom alebo nie. Dnes by som vám chcel na konkrétnom príklade ukázať, ako rieši podtitulok tohto blogu a teda, zistiť prvočísla na definovanom intervale prirodzených čísel, pričom hornú hranicu intervalu bude zadávať používateľ. Spodnou hranicou intervalu bude 0, ktorá samozrejme nie je prvočíslom a to z toho dôvodu, že prvočíslo je deliteľné číslom 1 a samým sebou. Z toho vyplýva, že 0, aj keď je deliteľná číslom 1, nie je deliteľná 0, pretože výraz 0/0 nie je definovaný. Hoci by si niekto myslel, že výsledok by mohol byť rovný číslu 1, nie je tomu tak. Nula proste nemôže deliť žiadny výraz.
Poďme teraz trochu ďalej. Už v minulom blogu som vyvodil záver, že ani 1 nie je prvočíslo a to preto, že je deliteľné 1 a sebou samým, čo je opäť číslo 1. A 1 a 1, nie sú dva rôzne faktory.
Podmienka, ktorá vylučuje, že 0 a 1 nie sú prvočísla, je samozrejme v mojom programe ošetrená. Čo ale ostatné čísla, ktoré sa nachádzajú na intervale, ktorého hornú hranicu zadal používateľ. Na túto otázku nám dá priamo odpoveď jednoduchý algoritmus, ktorý nesie názov Eratostenove sito.
Eratostenes z Kyrény bol okrem iného gréckym matematikom, ktorý pôsobil v dávnej Alexandrii približne 280 r. pred Kristom. Okrem toho, že vypočítal obvod zeme, definoval aj algoritmus, ktorý som pre vás implementoval vo vyššom programovacom jazyku C++.
Predtým, ako si detailne rozoberieme program napísaný v jazyku C++, si algoritmus ukážeme na nasledovných prirodzených číslach: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
Máme teda postupnosť, ktorá je na začiatku definovaná číslom 0 vrátane a na konci číslom 20, ktoré sa nachádza už mimo intervalu postupnosti. A to je práve tá horná hranica, ktorá bola vyššie spomenutá.
Umiestnime túto postupnosť do jednoriadkovej tabuľky, ktorá v mojom programe bude reprezentovaná vektorom celých čísel (vektor typu int).
Ako poznámku chcem dodať, že budeme teda používať triedu knižnice STL, ktorou je vektor. Vektor je entita, z ktorou sa lepšie manipuluje ako s poľom. Práve preto je tento článok určený tým čitateľom, ktorým je aspoň trochu známa problematika vektorov. Tým, ktorí nie sú oboznámení s problematikou vektorov, odporúčam najskôr preštudovať typ size_t, triedu vector a členskú metódu triedy vector push_back(). Potom sa s elánom môžu títo čitatelia pustiť do tohto blogu.
Ale naspäť k nášmu definovanému problému. Majme teda spomínanú postupnosť:[Image]
V tejto tabuľke vyznačme modrou farbou skutočnosť, že 0 a 1 nie sú prvočísla:[Image]
K indexom, na ktorých sa nachádzajú čísla 0 a 1 sa už teda nebudeme vracať. Poďme sa pozrieť na číslo 2. O tomto čísle vieme, že je najmenšie prvočíslo na tomto intervale, čo je prvotnou podmienkou k tomu, aby sme vyriešili podtitulok tohto blogu. Ostatné prvky (čísla) postupnosti budeme testovať Eratostenovym sitom – to znamená, že budeme teraz odstraňovať násobky čísla 2. Keďže číslo 3 nie je násobkom čísla 2, prejde Eratostenovym sitom. Zaznačme teda do tabuľky násobky čísla 2 červenou farbou.[Image]
Vidíme, že v jednom kroku odstránil algoritmus (Eratostenovo sito) čísla 4, 6, 8, 10, 12, 14, 16 a 18. Zároveň sa už nebudeme žiadnym spôsobom vracať k indexu čísla 2. S predchádzajúcej tabuľky je taktiež očividné, že číslo 3 je prvočíslom. Poďme teraz odstrániť z tabuľky jeho násobky a zaznačme túto skutočnosť zelenou farbou.[Image]
V ďalšom kroku nám algoritmus odstránil číslo 6, 9, 12, 15, 18, ktoré prvočíslami nie sú. Áno, zelenou farbou sme označili aj niektoré čísla, ktoré boli v predchádzajúcom kroku odstránené násobkom čísla 2. To však nemení nič na skutočnosti, že tento krok nám odstránil z postupnosti ďalšie čísla, ktorými sú čísla: 9 a 15. Po vykonaní spomínaného kroku vidíme, že číslo 5 ostalo vyznačené žltou farbou. Číslo 5 je teda prvočíslo, pretože prešlo Eratostenovym sitom. Keď by sme v nasledujúcom kroku odstránili násobky čísla 5. zistíme, že už boli čísla 10 a 15 odstránené násobkom iného čísla. Kedy sa teda algoritmus skončí ? Bude to vtedy, pokým sa skutočne nedostaneme k číslu 19. Číslo 19 už nemá za úlohu odstraňovať žiadny násobok, pretože sa za nim v našej tabuľke nič nenachádza. Dosiahnutie jeho indexu určitou interačnou premennou je podmienkou na skončenie algoritmu, hoci sa už v stave prvočísel alebo odstránených čísel nič nemení.
Vyberme teraz všetky čísla označené žltou farbou z našej tabuľky:[Image]
Ostanú nám čísla, ktoré sú zaiste prvočíslami. A tak sme sa dostali k výsledku nášho algoritmu, ktorými sú čísla 2, 3, 5, 7, 11, 13, 17 a 19. Pre kontrolu si môžete porovnať tieto čísla s prvočíslami uvedenými v iných zdrojoch, ale určite dostanete ten istý výsledok.
Poďme teraz do detailu rozobrať nasledujúci zdrojový kód napísaný v jazyku C++, ktorý je implementáciou verbálneho vysvetlenia algoritmu uvedeného vyššie. Jazyk C++ nám ponúka ďalšie možnosti, ako zefektívniť výpočet. Sú to napr. skoky v programe, ktoré môžeme vykonať pomocou kľúčových slov break a continue. Ale k tomu neskôr. Poďme pekne poporiadku od prvého riadku.
Na riadku 1 máme direktívou preprocesora pridaný hlavičkový súbor iostream.h. To znamená, že na tento riadok sa vloží obsah súboru iostream.h. Podobne máme na riadku 2 a 3 vložené tou istou direktívou hlavičkové súbory vector.h a string.h. Na riadku 4 je deklarované, že budeme v celom zdrojovom kóde, ktorý tvorí jeden súbor používať menný priestor std a teda ho nemusíme explicitne vo funkcii main volať, keď budeme z neho potrebovať nejakú triedu alebo objekt. Príkladom môžu byť objekt cin alebo cout. Na riadku 6 definujeme funkciu main a následne na riadku 7 začína jej telo. Na riadku 8 deklarujeme premennú integrálneho typu a to konkrétne char s identifikátorom premennej c_end. Táto premenná reprezentuje jeden znak, ktorý rozhodne o tom, či sa vonkajšia slučka po vykonaní vlastného algoritmu Eratostenovho sita ukončí alebo nie. Práve preto je na riadku 89 vyzvaný používateľ, aby stlačil kláves a alebo n. Ak potlačí n, program pokračuje ďalším cyklom while slučky. Ak potlačí iný kláves program sa skončí.
Na riadku 9 je definovaná nová inštancia triedy string s identifikátorom sz, ktorá je inicializovaná na prázdnu hodnotu.
Za touto inicializáciou je na riadku 10 uvedená deklarácia premennej iSZ na typ int bez ďalšej inicializácie.
Na riadku 11 deklarujeme premennú typu bool, ktorá bude v programe uchovávať informáciu, či používateľ na výzvu programu odpovedal zadaním validnej hodnoty (teda hodnoty integer), ktorá sa bude uchovávať v premennej iSZ. Ak používateľ zadá platnú vstupnú informáciu z okna konzolovej aplikácie, premenná is_size_t sa nastaví na true, v opačnom prípade (ak teda používateľ nezadá platnú hodnotu z rozsahu integer) premenná is_size_t sa nastaví na hodnotu false. Premenná is_size_t je na riadku prvotne inicializovaná na hodnotu false. To reprezentuje stav, že premenná iSZ nebola ešte inicializovaná a to je v skutočnosti pravda. Na riadku 13 je uvedené kľúčové slovo do. To znamená, že sa začína telo slučky do while, v ktorej je ako podmienka uvedená komparácia obsahu premennej c_end so znakom n (viď. riadok 95).
Keď program prejde ďalej, dostane sa na riadok 14, ktoré otvára telo spomínanej slučky do while, za ktorou na riadku 15 začína slučka while, čo znamená slučka s podmienkou na začiatku každého cyklu. Práve tu sa program pýta (porovnáva), či je v premennej uložená hodnota false. Ak áno, program pokračuje kladnou vetvou a vyzve na riadku 17, aby používateľ zadal hornú hranicu Eratostenovho sita. Táto hodnota sa nebude brať do úvahy pri testovaní čísla na prvočíslo. Na riadku 18 sa vstup zadaný používateľom načíta do premennej (objektu) sz, ktorá je novou inštanciou triedy string. Načítanie prebehne pomocou metódy getline(), ktorá má dva parametre a to objekt cin a objekt sz.
Na riadku 20 nasleduje blog kódu try a catch, ktoré slúžia na rozpoznanie validity hodnoty zadanej používateľom do objektu sz. Vo vetve try sa program pokúša konvertovať hodnotu v objekte sz na hodnotu celého čísla, ktoré reprezentuje dĺžku intervalu, na ktorom hľadáme Eratostenovym sitom všetky prvočísla. Na túto konverziu sa použije funkcia stoi, čo v skratke znamená string to integer (v slovenskom jazyku string na integer). Po konverzii sa na riadku 24 ešte testuje, či používateľ nezadal na vstupe číslo 0. Ak áno program nastaví premennú is_size_t na hodnotu false a skočí pomocou príkazu continue na opätovné vyhodnotene podmienky ďalšieho cyklu slučky while. Keďže v premennej is_size_t je opäť false program pokračuje v slučke while, kedy na riadku 17 je používateľ znova vyzvaný na zadanie hornej hranice intervalu Eratostenovho sita. Takto môže byť program zacyklený dovtedy, pokým používateľ nezadá platnú hodnotu na vstupe konzolovej aplikácie.
Poďme sa pozrieť teraz na to, keď používateľ nezadá hodnotu z rozsahu integrálneho typu (napr. neplatnú hodnotu “hsfu“). Už asi tušíte, že sa nejedná o hodnotu integrálneho typu, ale o nezmyselné znaky, ktoré síce môže používateľ zadať, pretože tieto hodnoty je možné priradiť typu string, ale konverzia tejto hodnoty na hodnotu typu integer sa nepodarí. Práve preto je v našom programe umiestnený na riadku 34 blok catch, ktorí túto výnimku zachytí. A čo sa vlastne stane ďalej ? No to isté, čo v prípade zadania 0, to znamená, že sa nastaví hodnota false do premennej is_size_t a program skočí pomocou príkazu continue na začiatok slučky while, kde sa opätovne v podmienke vyhodnotí, či má pokračovať výzvou používateľa na zadanie validnej hodnoty hornej hranice Eratostenovho sita, a keďže je negácia hodnoty v premennej is_size_t true, program aj tak urobí. A takto bude program dookola vyzývať používateľa na zadanie platnej hodnoty.
V prípade, že používateľ zadá platnú hodnotu, program skočí do vetvy try, kde potom skočí do zápornej vetvy príkazu if (klauzula else na riadku 29), kde sa už hodnota is_size_t nastaví na true. Tým pádom program v tomto cykle vyskočí so slučky while, pretože už nespĺňa podmienku na ďalšie vykonanie cyklu.
Keď používateľ zadal platnú hornú hranicu Eratostenovho sita, môže sa táto informácia použiť na alokáciu vektora o dĺžky iSZ (alokácia vektora s identifikátorom vNumberVektor), čo je implementované na riadku 41. Na riadku 42 je alokovaný vektor o dĺžke 0 (vektor s identifikátorom vPrimeVektor). Do tohto vektora budeme ukladať prvočísla, ktoré prejdú Eratostenovym sitom. Dĺžku 0 má vektor preto, že je možné do neho pridávať prvočíslo po prvočísle, až keď časť algoritmu učiní rozhodnutie, či číslo, ktoré sa vyberá z vektora vNumberVektor je prvočíslom alebo nie.
Na riadku 44 začína for slučka, ktorá je vo svojich jednotlivých cykloch riadená iteračnou premennou i, ktorá sa v každom cykle inkrementuje, až pokým nedosiahne hodnotu iSZ. Táto for slučka vo svojom tele napĺňa vektor vNumberVektor číslami od 0 po 19 (pretože horná hranica, ktorú sme vymedzili v ukážke je 20).
Vlastný algoritmus Eratostenovho sita začína na riadku 49, kde je iteračná premenná na začiatku cyklu inicializovaná na hodnotu 2. Prečo je tomu tak ? Pretože na prvých dvoch indexoch vektora (index 0 a 1) sú uložené čísla 0 a 1 a tie nepatria do množiny prvočísel. Toto je základná idioma, ktorú je potrebné si uvedomiť. Keby sme totiž delili nulou, program by vyhlásil chybu. Keby sme delili jednotkou, nedostali by sme nič iné ako pôvodné číslo. Práve preto sa testujú iba čísla od hodnoty 3. Prečo od 3, keď iterujeme od 2 ? Jedná sa o prvotnú podmienku, ktorú som spomínal. Ak teda číslo na indexe 2 sa bude rovnať 2, pridáme toto číslo do vektora vPrimeVektor, pretože o ňom vieme, že je najmenšie prvočíslo. Ostatné čísla už budeme testovať, to znamená, že ak bude index väčší alebo rovný 3, program testuje konkrétne číslo tak, že delí toto číslo číslami uloženými vo vektore vPrimeVektor (čo sú prvočísla) so zvyškom. To znamená, že berie do úvahy zvyšok po delení čísla prvočíslom. Ak je tento zvyšok po delení rôzny od nuly, našli sme ďalšie prvočíslo a to uložíme za vnútorným cyklom riadeným iteračnou premennou j (k tomu nám poslúži premenná typu bool, do ktorej pri nájdení prvočísla uložíme hodnotu true, ktorá indikuje tento stav), do vektora vPrimeVektor, ktorý reprezentuje hľadané prvočísla. Uložíme ho na posledný index pomocou metódy push_back, čo nám zároveň zaručuje usporiadanie hľadaných prvočísel od najmenšieho po najväčšie.
Ak by bol zvyšok po delení rovný nule, testované číslo nie je prvočíslom a to znamená, že nastavíme premennú flag na false, skočíme pomocou kľúčového slova break na koniec for slučky (iteračná premenná j). Do vektora vPrimeVektor sa v tomto prípade nič neuloží, pretože v premennej flag je uložené hodnota false. vonkajšia slučka for sa ukončí, keď sú otestované všetky čísla uložené vo vektore vNumberVektor. Posledným testovaným číslom je teda číslo 19.
Po otestovaní všetkých čísel nasleduje zápis prvočísel do okna konzolovej aplikácie (viď. riadok 78 až 83), na čo využijeme objekt cout a slučku for. K zápisu samozrejme patrí aj prechod kurzora na nový riadok na riadku 85.
Potom sa do okna konzolovej aplikácie zapíše výzva, ktorou sa program používateľa pýta, či chce program ukončiť alebo nie. Ak používateľ stlačí kláves n, program pokračuje a používateľ je vyzvaný na opätovné zadanie hornej hranice Eratostenovho sita s tým, že do premennej is_size_t sa opäť uloží hodnota false.
Ak by používateľ potlačil inú klávesu (čo znamená ukončenie programu), program skočí za vonkajšiu slučku while na riadok 97, funkcia main vráti operačnému systému 0 a celý program sa končí. Pripomínam, že na riadku 98 je pravá programová zátvorka, ktorá uzatvára telo funkcie main.
Výpis programu main.cpp
1: #include <iostream>
2: #include <vector>
3: #include <string>
4: using namespace std;
5:
6: int main()
7: {
8: char c_end;
9: string sz = "";
10: int iSZ;
11: bool is_size_t = false;
12:
13: do
14: {
15: while (!is_size_t)
16: {
17: cout << "Nacitaj hornu hranicu Eratostenovho sita: ";
18: getline(cin, sz);
19:
20: try
21: {
22: iSZ = stoi(sz);
23:
24: if (iSZ == 0)
25: {
26: is_size_t = false;
27: continue;
28: }
29: else
30: {
31: is_size_t = true;
32: }
33: }
34: catch (const std::exception&)
35: {
36: is_size_t = false;
37: continue;
38: }
39: }
40:
41: vector<int> vNumberVector(iSZ);
42: vector<int> vPrimeVector(0);
43:
44: for (int i = 0; i < (int)vNumberVector.size(); i++)
45: {
46: vNumberVector.at(i) = i;
47: }
48:
49: for (int i = 2; i < (int)vNumberVector.size(); i++)
50: {
51: if (i == 2)
52: {
53: vPrimeVector.push_back(vNumberVector.at(i));
54: }
55: else
56: {
57: bool flag = false;
58: for (int j = 0; j < (int)vPrimeVector.size(); j++)
59: {
60: if (vNumberVector.at(i) % vPrimeVector.at(j) != 0)
61: {
62: flag = true;
63: }
64: else
65: {
66: flag = false;
67: break;
68: }
69: }
70:
71: if (flag)
72: {
73: vPrimeVector.push_back(vNumberVector.at(i));
74: }
75: }
76: }
77:
78: cout << "Vypis prvocisel:" << endl;
79: cout << "----------------" << endl;
80: for (int i = 0; i < (int)vPrimeVector.size(); i++)
81: {
82: cout << vPrimeVector.at(i) << " ";
83: }
84:
85: cout << endl;
86:
87: cout << "Chces skoncit [a/n]: ";
88:
89: cin >> c_end;
90: cout << endl << endl;
91:
92: cin.ignore();
93: is_size_t = false;
94:
95: } while (c_end == 'n');
96:
97: return 0;
98: }Okno konzolovej aplikácie pri hornej hranici Eratostenovho sita 20[Image]
Na obrázku možno vidieť, že výsledné prvočísla sa stotožňujú s prvočíslami, ktoré sme vypočítali analytickým spôsobom (viď. posledná tabuľka v texte).
Dúfam, že vás príklad a program s Eratostenovym sitom zaujal, stačí už len, aby ste si to implementovali na svojom počítači.
Tento blog napísaI lektor C++ kurzov Marek ŠURKA. Ak máš nejaké otázky, napíš ich do komentárov.
