Základy programování Úloha: Eratosthenovo síto
Autor: Datum:
Josef Hrabal 28.11.2009
Číslo: Předmět:
HRA0031 ZAP
Obsah 1 Zadání úkolu: 1.1 Zadání: . . . . . . . 1.2 Neformální zápis: . 1.3 Příklad: . . . . . . 1.4 Tabulka: . . . . . . 1.5 Odkazy k projektu:
. . . . .
3 3 3 3 4 4
2 Uživatelské rozhraní 2.1 Program: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Výstupní soubor: . . . . . . . . . . . . . . . . . . . . . . . . .
5 5 7
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
3 Zdrojový kód: 8 3.1 V jazyce C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Vývojový diagram: . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Závěr 11 4.1 Seznam použitého software: . . . . . . . . . . . . . . . . . . . 11 4.2 Seznam zdrojů informací: . . . . . . . . . . . . . . . . . . . . . 11
2
1
Zadání úkolu:
1.1
Zadání:
Vaším úkolem je naprogramovat klasický algoritmus pro nalezení všech prvočísel z daného intervalu. Tento algoritmus je znám od starověku a za autora je pokládán matematik a filozof Eratosthénés z Kyrény. Princip algoritmu je velice jednoduchý spočívá v postupné eliminaci násobků čísel posloupnosti přirozených čísel tak, že nakonec v ní zůstanou jen prvočísla.
1.2
Neformální zápis:
1. Zapíšeme do posloupnosti všechna přirozená čísla od 2 do zvoleného n. Čísla 0 a 1 nejsou považována za prvočísla. 2. První neoznačené číslo v posloupnosti je prvočíslo. Toto číslo si označíme. 3. Z posloupnosti vyškrtámev šechny jeho násobky. 4. Pokud je v posloupnosti nějaké neoznačené číslo, pokračuj bodem 2.
1.3
Příklad:
Pro n=20 je postup výpočtu zobrazen v tabulce. Z tabulky je dále vidět, že Počínaje číslem 5 již nedojde k žádnému vyškrtávání násobků, protože případné Násobky již byly vyloučeny jako násobky čísel nižších, například 15 bylo vyloučeno jako násobek čísla 3. Obecně nemusíme√odstraňovat násobky čísel větších než odmocnina z n, v našem případě 5 > 2 20. V programu můžeme reprezentovat posloupnost nejjednodušeji polem logických hodnot. Jednotlivá čísla v posloupnosti nereprezentují hodnoty prvků v poli, ale indexy v tomto poli. Hodnota true pak znamená, že číslo odpovídající danému indexu je stále zařazeno v posloupnosti. Na hodnotu false prvek nastavíme při jeho vyškrtnutí z posloupnosti. Dále pro zjednodušení implementace se v poli ponechávají prvky s indexy 0 a 1, které označíme ihned jako vyškrtnuté, false . 3
Další možností implementace posloupnosti je pole bitů. Jednotlivá čísla jsou reprezentována bity. V případě, že pro uchování bitů použijeme typ int, který má 32 bitů, budou čísla 0 až 31 uložena jako bity 0 až 31 prvního prvku pole čísel typu int, čísla 32 až 63 bude uloženo jako bity 0 až 31 druhého prvku pole čísel typu int a tak dále. Dojde tedy k osminásobnému snížení paměťových nároků.
1.4
Tabulka:
2
3
2
2
2
5
6
3
5
označíme číslo 2 a vyloučíme jeho násobky 7 9 11 13 15 17
19
3
5
označíme číslo 3 a vyloučíme jeho násobky 7 11 13 15 17
19
5
označíme číslo 5 a vyloučíme jeho násobky 7 11 13 17
19
5
označíme číslo 7 a vyloučíme jeho násobky 7 11 13 17
19
3
2
3
1.5
4
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Odkazy k projektu:
• Webová prezentace k projektu: www.kilodelta.wz.cz/x-files • Wikipedia: www.cs.wikipedia.org/wiki/Eratosthenovo síto
4
2 2.1
Uživatelské rozhraní Program:
Uživatelské rozhrani je velmi jednoduché a intuitivní. Je napsáno kompletně v textovém režimu. Po spuštění se vás program zeptá, do kterého čísla chcete, aby se prvočísla generovala. Platná volba je od 2 do 32767. Názorně to lze vidět na obr.1.
obr.1 Po potvrzení volby se vypíšou vygenerované čísla oddělené čárkou. Po výpisu se zobrazí celkový počet nalezených prvočísel a volba, jestli chcete zapsat vygenerovaná prvočísla do souboru. Pokud ano zadáme Y(y), pokud ne, stačí napsat jakékoliv jiné písmeno. Viz. obr.2.
5
obr.2 Pokud jste zvolili, že chcete výsledek zapsat do souboru, program se vás zeptá na název souboru. Název souboru se musí zadat i s příponou. Název souboru jde zadat i s cestou pro případ, že byste chtěli soubor uložit jinam, než do složky s programem. Zadání názvu souboru jde vidět na obr.3.
obr.3 6
Nyní program ukončíte stisknutím jakékoliv klávesy.
obr.4 Webová prezentace k projektu je na adrese: www.kilodelta.wz.cz/x-files
2.2
Výstupní soubor:
Tady je ukázka výstupního souboru: Eratosthenovo sito, generuje prvocisla od 2 do n. (c)Josef Hrabal 24.11.2009 Zvolene n=100 Prvocisla : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, Konec vypisu.
7
3 3.1
Zdrojový kód: V jazyce C++
#include
; #include <math.h>; using namespace std; int main() { double max=0; //Proměnná pro načtění hodnoty do které se budou prvočísla generovat. int next=2; //Proměnná určující další nevyřazené prvočíslo v pořadí. int num=0; //Proměnná uchovává celkový počet nalezených prvočísel. bool primenumber[32768]; //Pole proměnných typu boolean určuje zda je dané čislo prvočíslo. cout « ”Eratosthenovo sito, generuje prvocisla od 2 do n. (c)Josef Hrabal 24.11.2009” « endl; //V následujícím cyklu se načítá proměnná max, která určuje do jakého čísla se budou prvočísla generovat. //Cyklus je použit z důvodu ošetření proti zadání chybné hodnoty. Přípustné hodnoty jsou čísla mezi 2 a 32767. //Při zadání chybného čísla se cyklus opakuje a zároveň je vypsána chybová hláška. do { cout « ”Do ktereho cisla ? (max 32767) : ”; cin » max; if ((max<2)||(max>32767)) { cout « ”Zadane cislo je mimo rozsah!” « endl; } } while ((max<2)||(max>32767)); //Zde celé pole nastavíme na true. for (int i=2; i<=max; i++) { primenumber[i]=true; } //Nyní přichází na řadu vlastní algoritmus na vyhledání prvočísel. //Pracuje na principu postupné eliminace všech násobků prvočísel, //dokud následující prvočíslo není větší než odmocnina z čísla do kterého prvočísla hledáme. while(next<=sqrt(max)) { //Odstraníme všechny násobky prvočísla. for (int i=(next*2); i<=max; i=i+next) { primenumber[i]=false; } int i=next; //Nyní vyhledáme další nevyřazené prvočíslo v pořadí. do { i++; next=i; }
8
while(primenumber[i]==false); } //Přichází na řadu výpis nalezených prvočísel. Zároveň zjistíme i jejich počet. for (int i=2; i¡=max; i++) { if (primenumber[i]==true) { cout « i « ”, ”; num++; } } //Zde již vypíšeme počet prvočísel a zároveň se uživatele zeptáme, zda chce nalezená prvočísla zapsat do souboru. cout « endl « ”Pocet prvocisel : ” « num « endl; cout « ”Zapsat vysledek do souboru? (Y/n): ”; char chr; cin » chr; //Pokud uživatel chce zapsat nalezená prvočísla pokračujeme v programu, jinak se následující část programu přeskočí. if ((chr==’Y’)——(chr==’y’)) { char soubor[255]; //Proměnná pro uložení názvu souboru, připadně i cesty k souboru. cout « ”Zadejte nazev souboru i s priponou : ”; cin » soubor; FILE *fr; //Otevřeme soubor pro zápis. Pokud soubor existuje, bude přepsán. Pokud neexistuje bude vytvořen. //Následně do souboru zapíšeme všechna prvočísla v podobném stylu jako na obrazovku. fr = fopen(soubor, ”wb”); fprintf(fr, ”Eratosthenovo sito, generuje prvocisla od 2 do n. (c)Josef Hrabal 24.11.2009\n”); fprintf(fr, ”Zvolene n=”); fprintf(fr, ”%.0f”, max); fprintf(fr, ”\nPrvocisla : ”); for (int i=2; i¡=max; i++) { if (primenumber[i]==true) { fprintf(fr, ”%i”, i); fprintf(fr, ”, ”); num++; if (num%15==0)//Rozdělení maximálně 15 čísel na řádek. { fprintf(fr, ”\n”); } } } fprintf(fr, ”\nKonec vypisu.”); fclose(fr);//Uzavření souboru. } cin.get(); return 0; }
9
3.2
Vývojový diagram:
10
4
Závěr
4.1
Seznam použitého software:
• Microsoft Windows 7 Professional • Microsoft Visual C++ 2008 Express Edition • TeX Live! 2009 • PSPad version 4.5.4 • DiaCZE version 0.95-1 • Foxit Reader version 3.1.2.1013 • EasyPHP version 1.8.0.1 • Mozilla Firefox version 3.5.5
4.2
Seznam zdrojů informací:
• Webová prezentace k projektu: www.kilodelta.wz.cz/x-files • Zadání projektu: www.cs.vsb.cz • Ne příliš stučný úvod od systému LATEX2e: Tobias Oetiker • Příručka LATEX: www.cstug.cz/latex/lm • Wikipedia: www.cs.wikipedia.org • Jak Psát Web: www.jakpsatweb.cz
11
