{{indexmenu_n>2}} ======== HW 02 - Prvočíselný rozklad ======== ^ Termín odevzdání | 10.03.2018 23:59 PST | ^ Povinné zadání | 2b | ^ Volitelné zadání | 4b| ^ Bonusové zadání | není | ^ Počet uploadů | 10 | Implementujte program, který načte ze standardního vstupu seznam celých kladných čísel zakončený nulou a provede jejich prvočíselný rozklad. Vstupní čísla jsou na jednotlivých řádcích. Číslo 1 je speciální případ vstupu, při kterém vypište 1 jako "prvočíselný rozklad". Pokud bude na vstupu záporné číslo nebo jiný neočekávaný vstup, vypiště chybovou hlášku "''Error: Chybny vstup!''" na standardní chybový výstup a ukončete program s návratovou hodnotou ''100''. ==== Příklad 1 - pub01-m ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 1 11 120 8 0 | Prvociselny rozklad cisla 1 je: 1 Prvociselny rozklad cisla 11 je: 11 Prvociselny rozklad cisla 120 je: 2^3 x 3 x 5 Prvociselny rozklad cisla 8 je: 2^3 | žádný | 0 | ==== Příklad 2 - pub02-m ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 12 -2 100 0 | Prvociselny rozklad cisla 12 je: 2^2 x 3 | Error: Chybny vstup! | 100 | ==== Příklad 3 - pub03-m ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 12 b 100 0 | Prvociselny rozklad cisla 12 je: 2^2 x 3 | Error: Chybny vstup! | 100 | ==== Příklad 4 - pub04-m ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 991350783547 0 | Prvociselny rozklad cisla 991350783547 je: 995663 x 995669 | žádný | 0 | ====== Povinné zadání ====== Na vstupu jsou pouze celá čísla, která jsou reprezentovatelná pomocí 64-bitového celočíselného znamenkového typu. Vzhledem k náročnosti úkolu předpokládáme, že největší číslo v prvočíselném rozkladu je menší než $10^6$. Aby byl váš algoritmus efektivní pro opakovaná volání, tak si předpočítejte tabulku všech prvočísel do hodnoty $10^6$ algoritmem [[https://cs.wikipedia.org/wiki/Eratosthenovo_s%C3%ADto|Eratosthenovo síto]]. Následně je možné zkoušet dělení pouze nalezenými prvočísly a významně tak výpočet urychlit. Doporučení: Pro uložení nalezených prvočísel používejte "pouze" 32-bitový celočíselný znamenkový typ. ====== Příklad časové náročnosti ====== Rychlost vašecho programu pro volitelnou část můžete testovat například na rozkladu číselné řady od 1 do N. Výpočetní časy různých verzí programu spuštěných na standardním počítači((Notebook, Intel Core i5 CPU M480 @ 2.67 GHz, 8GB RAM DDR3 1066 MHz.)) a zkompilovaných se zapnutou optimalizací (-O3) jsou zaznamenány v následující tabulce. Pro představu jsme otestovali i instance opt01 až opt03 z odevzdávacího systému. V přepočtu na rychlost počítače v odevzdávacím systému odpovídá časový limit přibližně 1.8 až 2 s pro volitelné úlohy opt*. ^ Řešení / Vstupní soubor ^ 1-10000 ^ 1-50000 ^ 1-100000 ^ opt01 ^ opt02 ^ opt03 ^ | Naivní I | 0.18 s | 3.0 s | 11.6 s | 4.6 s | DNF ((Více než 10 minut.)) | DNF ((Více než 10 minut.)) | | Naivní II | 0.16 s | 2.3 s | 8.8 s | 4.3 s | 4.4 s | 4.6 s | | Referenční | 0.04 s | 0.3 s | 1.1 s | 0.4 s | 0.4 s | 0.4 s | ==== Naivní řešení I ==== Vstupní číslo zkouší dělit všemi čísly menšími než je vstupní číslo. ==== Naivní řešení II ==== Vstupní číslo zkouší dělit všemi menšími čísly. Algoritmus končí, když je dělenec menší než dělitel. ==== Referenční řešení ==== Využívá předpočítaná prvočísla do hodnoty $10^6$. Algoritmus končí, když je dělenec menší než dělitel. ==== Testovací instance na rychlost výpočtu ==== ^ Zkratka testu ^ Popis ^ | man05 | Přibližně 8000 čísel, které jsou většinou prvočísly z intervalu 2 až 100000. | | man06 | Přibližně 7000 čísel, které jsou většinou složené ze dvou prvočísel z intervalu 2 až 100000. | | man07 | Přibližně 300 čísel, které jsou většinou složené ze dvou prvočísel v intervalu 900000 až 1000000. | Neukládejte prvočísla přímo do zdrojového kódu, **maximální velikost souboru ''main.c'' je 50 kB**. ====== Volitelné zadání [-prg-optional] ====== Program je ve volitelné části spuštěn s argumentem '-prg-optional'. Na vstupu mohou být celá kladná čísla dlouhá až 100 cifer. Je tedy nutné vytvořit jejich vlastní reprezentaci v počítači spolu s příslušnými operacemi celočíselného dělení se zbytkem. Největší číslo v prvočíselném rozkladu bude vždy menší než $10^6$. Při implementaci nepoužívejte cízí kód ani žádnou specializovanou knihovnu pro práci s velkými čísly. V tomto úkolu nemusíte používat Eratostenovo síto, protože časový limit nebude nijak přísný. Cílem je především práce s velkými čísly. ==== Příklad 5 - pub01-o ==== Rozkládané číslo((Je možné si ověřit na [[https://www.wolframalpha.com/input/?i=(995663+*+995669)%5E8|Wolfram Alpha - výpočet]].)) je $(995663 * 995669)^8$: ^ Vstup | 932865073719992059629773513614789388266580305083920591925740371392254317064584855785088915745761 0 | ^ Výstup | Prvociselny rozklad cisla 932865073719992059629773513614789388266580305083920591925740371392254317064584855785088915745761 je: 995663^8 x 995669^8 | Výpočetní čas na běžném počítači (bez optimalizace): real 0m1.279s user 0m1.264s sys 0m0.004s Časový limit v odevzdávacím systému je přibližně desetinásobek referenčního programu (10s). ====== Odevzdání ====== U tohoto domácího úkolu je linkována matematická knihovna **''''** a to přepínačem **''-lm''**. Veřejné příklady + Makefile: {{:courses:b3b36prg:hw:prg-hw02.zip|}} ^ ^ Povinné zadání ^ Volitelné zadání ^ ^ Název v BRUTE | HW02 || ^ Odevzdávané soubory | main.c, *.h ((Jeden soubor main.c může používat více hlavičkových souborů. Nevytvářejte žádné složky.)) || ^ Argumenty při spuštění | žádné | -prg-optional | ^ Kompilace pomocí | clang -pedantic -Wall -Werror -std=c99 -O3 -lm || ^ Očekávaná časová složitost((Rozklad jednoho vstupního čísla v závislosti na jeho velikosti $v$. Časová složitost u volitelné části je dána počtem prvočísel do zadané hodnoty $v$ ([[https://en.wikipedia.org/wiki/Prime_number|Prime number]]).)) | $\approx \mathcal{O}\left(\dfrac{v}{\log{}v}\right)$ | $\approx \mathcal{O}\left(\dfrac{v}{\log{}v}\right)$ | ^ Procvičované oblasti | pole | pole |