Eratostenovo síto

V předchozím blogujsme se zabývali prvočísly. Ukázali jsme si ukázku programu, který rozeznal, zda zadané číslo je prvočíslem nebo ne. Dnes bych vám chtěl na konkrétním příkladu ukázat, jak řeší podtitulek tohoto blogu a tedy zjistit prvočísla na definovaném intervalu přirozených čísel, přičemž horní hranici intervalu bude zadávat uživatel. Spodní hranicí intervalu bude 0, která samozřejmě není prvočíslem a to z toho důvodu, že prvočíslo je dělitelné číslem 1 a sebou samým. Z toho vyplývá, že 0, i když je dělitelná číslem 1, není dělitelná 0, protože výraz 0/0 není definován. Přestože by si někdo myslel, že výsledek by mohl být roven číslu 1, není tomu tak. Nula prostě nemůže dělit žádný výraz.
Pojďme teď trochu dál. Už v minulém blogu jsem vyvodil závěr, že ani 1 není prvočíslo a to proto, že je dělitelné 1 a sebou samým, což je opět číslo 1. A 1 a 1, nejsou dva různé faktory.
Podmínka, která vylučuje, že 0 a 1 nejsou prvočísla, je samozřejmě v mém programu ošetřena. Co ale ostatní čísla, která se nacházejí na intervalu, jehož horní hranici zadal uživatel. Na tuto otázku nám přímo dá odpověď jednoduchý algoritmus, který nese název Eratostenovo síto.
Eratostenes z Kyrény byl mimo jiné řeckým matematikem, který působil v dávné Alexandrii přibližně 280 let. před Kristem. Kromě toho, že vypočítal obvod země, definoval také algoritmus, který jsem pro vás implementoval ve vyšším programovacím jazyce C++.
Předtím, než si detailně rozebereme program napsaný v jazyce C++, si algoritmus ukážeme na následujících přirozených číslech: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
Máme tedy posloupnost, která je na začátku definována číslem 0 včetně a na konci číslem 20, které se nachází již mimo intervalu posloupnosti. A to je právě ta horní hranice, která byla výše zmíněna.
Umístíme tuto posloupnost do jednořádkové tabulky, která v mém programu bude reprezentována vektorem celých čísel (vektor typu int).
Jako poznámku chci dodat, že budeme tedy používat třídu knihovny STL, kterou je vektor. Vektor je entita, z níž se lépe manipuluje než s polem. Právě proto je tento článek určen těm čtenářům, kterým je alespoň poněkud známá problematika vektorů. Těm, kteří nejsou obeznámeni s problematikou vektorů, doporučuji nejprve prostudovat typ size_t, třídu vector a členskou metodu třídy vector push_back(). Potom se s elánem mohou tito čtenáři pustit do tohoto blogu.
Ale zpět k našemu definovanému problému. Mějme tedy zmiňovanou posloupnost:

V této tabulce vyznačme modrou barvou skutečnost, že 0 a 1 nejsou prvočísla:

K indexům, na kterých se nacházejí čísla 0 a 1 se už tedy nebudeme vracet. Pojďme se podívat na číslo 2. O tomto čísle víme, že je nejmenší prvočíslo na tomto intervalu, což je prvotní podmínkou k tomu, abychom vyřešili podtitulek tohoto blogu. Ostatní prvky (čísla) posloupnosti budeme testovat Eratostenovým sítem – to znamená, že budeme nyní odstraňovat násobky čísla 2. Jelikož číslo 3 není násobkem čísla 2, projde Eratostenovým sítem. Zaznačme tedy do tabulky násobky čísla 2 červenou barvou.

Vidíme, že v jednom kroku odstranil algoritmus (Eratostenovo síto) čísla 4, 6, 8, 10, 12, 14, 16 a 18. Zároveň se již nebudeme žádným způsobem vracet k indexu čísla 2. S předchozí tabulky je také očividné, že číslo 3 je prvočíslem. Pojďme nyní odstranit z tabulky jeho násobky a zaznačme tuto skutečnost zelenou barvou.

V dalším kroku nám algoritmus odstranil číslo 6, 9, 12, 15, 18, které prvočísly nejsou. Ano, zelenou barvou jsme označili i některá čísla, která byla v předchozím kroku odstraněna násobkem čísla 2. To však nemění nic na skutečnosti, že tento krok nám odstranil z posloupnosti další čísla, kterými jsou čísla: 9 a 15. Po provedení zmiňovaného kroku vidíme , že číslo 5 zůstalo vyznačeno žlutou barvou. Číslo 5 je tedy prvočíslo, protože prošlo Eratostenovým sítem. Když bychom v následujícím kroku odstranili násobky čísla 5. zjistíme, že již byla čísla 10 a 15 odstraněna násobkem jiného čísla. Kdy tedy algoritmus skončí? Bude to tehdy, dokud se skutečně nedostaneme k číslu 19. Číslo 19 už nemá za úkol odstraňovat žádný násobek, protože se za ním v naší tabulce nic nenachází. Dosažení jeho indexu určitou interační proměnnou je podmínkou pro skončení algoritmu, ačkoli se již ve stavu prvočísel nebo odstraněných čísel nic nemění.
Vyberme nyní všechna čísla označená žlutou barvou z naší tabulky:

Zůstanou nám čísla, která jsou zajisté prvočísly. A tak jsme se dostali k výsledku našeho algoritmu, kterými jsou čísla 2, 3, 5, 7, 11, 13, 17 a 19. Pro kontrolu si můžete porovnat tato čísla s prvočísly uvedenými v jiných zdrojích, ale určitě dostanete tentýž výsledek.
Pojďme nyní do detailu rozebrat následující zdrojový kód napsaný v jazyce C++, který je implementací verbálního vysvětlení algoritmu uvedeného výše. Jazyk C++ nám nabízí další možnosti, jak zefektivnit výpočet. Jsou to například. skoky v programu, které můžeme provést pomocí klíčových slov break a continue. Ale k tomu později. Pojďme pěkně popořadě od prvního řádku.
Na řádku 1 máme direktivou preprocesoru přidaný hlavičkový soubor iostream.h. To znamená, že do tohoto řádku se vloží obsah souboru iostream.h. Podobně máme na řádku 2 a 3 vloženy stejnou direktivou hlavičkové soubory vector.h a string.h. Na řádku 4 je deklarováno, že budeme v celém zdrojovém kódu, který tvoří jeden soubor používat jmenný prostor std a tudíž jej nemusíme explicitně ve funkci main volat, když budeme z něj potřebovat nějakou třídu nebo objekt. Příkladem mohou být objekt cin nebo cout. Na řádku 6 definujeme funkci main a následně na řádku 7 začíná její tělo. Na řádku 8 deklarujeme proměnnou integrálního typu a to konkrétně char s identifikátorem proměnné c_end. Tato proměnná reprezentuje jeden znak, který rozhodne o tom, zda se vnější smyčka po provedení vlastního algoritmu Eratostenova síta ukončí nebo ne. Právě proto je na řádku 89 vyzván uživatel, aby stiskl klávesu a nebo n. Pokud potlačí n, program pokračuje dalším cyklem while smyčky. Pokud potlačí jinou klávesu program skončí.
Na řádku 9 je definována nová instance třídy string s identifikátorem sz, která je inicializována na prázdnou hodnotu.
Za touto inicializací je na řádku 10 uvedena deklarace proměnné iSZ na typ int bez další inicializace.
Na řádku 11 deklarujeme proměnnou typu bool, která bude v programu uchovávat informaci, zda uživatel na výzvu programu odpověděl zadáním validní hodnoty (tedy hodnoty integer), která se bude uchovávat v proměnné iSZ. Pokud uživatel zadá platnou vstupní informaci z okna konzolové aplikace, proměnná is_size_t se nastaví na true, v opačném případě (pokud tedy uživatel nezadá platnou hodnotu z rozsahu integer) proměnná is_size_t se nastaví na hodnotu false. Proměnná is_size_t je na řádku prvotně inicializována na hodnotu false. To reprezentuje stav, že proměnná iSZ nebyla ještě inicializována a to je ve skutečnosti pravda. Na řádku 13 je uvedeno klíčové slovo do. To znamená, že začíná tělo smyčky do while, ve které je jako podmínka uvedena komparace obsahu proměnné c_end se znakem n (viz. řádek 95).
Když program přejde dál, dostane se na řádek 14, které otevírá tělo zmíněné smyčky do while, za kterou na řádku 15 začíná smyčka while, což znamená smyčka s podmínkou na začátku každého cyklu. Právě zde se program ptá (srovnává), zda je v proměnné uložena hodnota false. Pokud ano, program pokračuje kladnou větví a vyzve na řádku 17, aby uživatel zadal horní hranici Eratostenova síta. Tato hodnota nebude brána v úvahu při testování čísla na prvočíslo. Na řádku 18 se vstup zadaný uživatelem načte do proměnné (objektu) sz, která je novou instancí třídy string. Načtení proběhne pomocí metody getline(), která má dva parametry a to objekt cin a objekt sz.
Na řádku 20 následuje blog kódu try a catch, které slouží k rozpoznání validity hodnoty zadané uživatelem do objektu sz. Ve větvi try se program pokouší konvertovat hodnotu v objektu sz na hodnotu celého čísla, které reprezentuje délku intervalu, na kterém hledáme Eratostenovým sítem všechna prvočísla. Pro tuto konverzi se použije funkce stoi, což ve zkratce znamená string to integer (v českém jazyce string na integer). Po konverzi se na řádku 24 ještě testuje, zda uživatel nezadal na vstupu číslo 0. Pokud ano program nastaví proměnnou is_size_t na hodnotu false a skočí pomocí příkazu continue na opětovně vyhodnocené podmínky dalšího cyklu smyčky while. Jelikož v proměnné is_size_t je opět false program pokračuje ve smyčce while, kdy na řádku 17 je uživatel znovu vyzván k zadání horní hranice intervalu Eratostenova síta. Takto může být program zacyklen, dokud uživatel nezadá platnou hodnotu na vstupu konzolové aplikace.
Pojďme se podívat nyní na to, když uživatel nezadá hodnotu z rozsahu integrálního typu (např. neplatnou hodnotu „hsfu“). Již asi tušíte, že se nejedná o hodnotu integrálního typu, ale o nesmyslné znaky, které sice může uživatel zadat, protože tyto hodnoty lze přiřadit typu string, ale konverze této hodnoty na hodnotu typu integer se nezdaří. Právě proto je v našem programu umístěn na řádku 34 blok catch, kteří tuto výjimku zachytí. A co se vlastně stane dál? No totéž, co v případě zadání 0, to znamená, že se nastaví hodnota false do proměnné is_size_t a program skočí pomocí příkazu continue na začátek smyčky while, kde sa znovu v podmínce vyhodnotí, zda má pokračovat výzvou uživatele k zadání validní hodnoty horní hranice Eratostenova síta, a jelikož je negace hodnoty v proměnné is_size_t true, program i tak učiní. A takto bude program dokola vyzývat uživatele k zadání platné hodnoty.
V případě, že uživatel zadá platnou hodnotu, program skočí do větve try, kde pak skočí do záporné větve příkazu if (klauzule else na řádku 29), kde se již hodnota is_size_t nastaví na true. Tím pádem program v tomto cyklu vyskočí ze smyčky while, protože již nesplňuje podmínku pro další provedení cyklu.
Když uživatel zadal platnou horní hranici Eratostenova síta, může se tato informace použít k alokaci vektoru o délce iSZ (alokace vektoru s identifikátorem vNumberVektor), což je implementováno na řádku 41. Na řádku 42 je alokován vektor o délce 0 (vektor s identifikátorem) . Do tohoto vektoru budeme ukládat prvočísla, která projdou Eratostenovým sítem. Délku 0 má vektor proto, že je možné do něj přidávat prvočíslo po prvočísle, až když část algoritmu učiní rozhodnutí, zda číslo, které se vybírá z vektoru vNumberVektor je prvočíslem nebo ne.
Na řádku 44 začíná for smyčka, která je ve svých jednotlivých cyklech řízena iterační proměnnou i, která se v každém cyklu inkrementuje, dokud nedosáhne hodnoty iSZ. Tato for smyčka ve svém těle naplňuje vektor vNumberVektor čísly od 0 po 19 (protože horní hranice, kterou jsme vymezili v ukázce je 20).
Vlastní algoritmus Eratostenova síta začíná na řádku 49, kde je iterační proměnná na začátku cyklu inicializována na hodnotu 2. Proč je tomu tak? Protože na prvních dvou indexech vektoru (index 0 a 1) jsou uložena čísla 0 a 1 a ta nepatří do množiny prvočísel. Toto je základní idioma, kterou je třeba si uvědomit. Kdybychom totiž dělili nulou, program by vyhlásil chybu. Kdybychom dělili jedničkou, nedostali bychom nic jiného než původní číslo. Právě proto se testují pouze čísla od hodnoty 3. Proč od 3, když iterujeme od 2? Jedná se o prvotní podmínku, kterou jsem zmiňoval. Pokud tedy číslo na indexu 2 se bude rovnat 2, přidáme toto číslo do vektoru vPrimeVektor, protože o něm víme, že je nejmenší prvočíslo. Ostatní čísla už budeme testovat, to znamená, že pokud bude index větší nebo roven 3, program testuje konkrétní číslo tak, že dělí toto číslo čísly uloženými ve vektoru vPrimeVektor (což jsou prvočísla) se zbytkem. To znamená, že bere v úvahu zbytek po dělení čísla prvočíslem. Pokud je tento zbytek po dělení různý od nuly, našli jsme další prvočíslo a to uložíme za vnitřním cyklem řízeným iterační proměnnou j (k tomu nám poslouží proměnná typu bool, do které při nalezení prvočísla uložíme hodnotu true, která indikuje tento stav), do vektoru vPrimeVektor, který reprezentuje hledaná prvočísla. Uložíme jej na poslední index pomocí metody push_back, což nám zároveň zaručuje uspořádání hledaných prvočísel od nejmenšího po největší.
Pokud by byl zbytek po dělení roven nule, testované číslo není prvočíslem a to znamená, že nastavíme proměnnou flag na false, skočíme pomocí klíčového slova break na konec for smyčky (iterační proměnná j). Do vektoru vPrimeVektor se v tomto případě nic neuloží, protože v proměnné flag je uložena hodnota false. vnější smyčka for se ukončí, když jsou otestována všechna čísla uložená ve vektoru vNumberVektor. Posledním testovaným číslem je tedy číslo 19.
Po otestování všech čísel následuje zápis prvočísel do okna konzolové aplikace (viz. řádek 78 až 83), k čemuž využijeme objekt cout a smyčku for. K zápisu samozřejmě patří také přechod kurzoru na nový řádek na řádku 85.
Potom se do okna konzolové aplikace zapíše výzva, kterou se program uživatele ptá, zda chce program ukončit nebo ne. Pokud uživatel stiskne klávesu n, program pokračuje a uživatel je vyzván k opětovnému zadání horní hranice Eratostenova síta s tím, že do proměnné is_size_t se opět uloží hodnota false.
Pokud by uživatel potlačil jinou klávesu (což znamená ukončení programu), program skočí za vnější smyčku while na řádek 97, funkce main vrátí operačnímu systému 0 a celý program končí. Připomínám, že na řádku 98 je pravá programová závorka, která uzavírá tělo funkce 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 konzolové aplikace u horní hranice Eratostenova síta 20

Na obrázku lze vidět, že výsledná prvočísla se ztotožňují s prvočísly, které jsme vypočítali analytickým způsobem (viz. poslední tabulka v textu).
Doufám, že vás příklad a program s Eratostenovým sítem zaujal, stačí už jen, abyste si to implementovali na svém počítači.
Tento blog napsal lektor C++ kurzů Marek ŠURKA. Pokud máš nějaké dotazy, napiš je do komentářů.