{{indexmenu_n>5}} ======== HW 04 - Prvočíselný rozklad ======== ^ Termín odevzdání | 30.10.2021 23:59 \\ Bonusová úloha - 08.01.2022 23:59 PST(([[https://www.timeanddate.com/time/zones/pst|PST]])) | ^ Povinné zadání | 2b kontrola [[courses:b0b36prp:resources:tessun:start|Coding Stylu]]| ^ Volitelné zadání | 3b kontrola [[courses:b0b36prp:resources:tessun:start|Coding Stylu]]| ^ Bonusové zadání | **5b** kontrola [[courses:b0b36prp:resources:tessun:start|Coding Stylu]]| ^ Počet uploadů | 20 | ^ Podpůrné soubory | {{:courses:b0b36prp:hw:b0b36prp-hw04.zip|}} | U této úlohy bude cvičící ručně hodnotit dodržení [[courses:b0b36prp:resources:tessun:start|Coding Stylu]]. Hodnocení je popsáno [[courses:b0b36prp:hw:start|zde]]. Možná vám to dosud nepřišlo, ale relativně značná část řešení domácích úkolů nespočívá v samotném kódování, ale v přípravě, tj. čtení a pochopení zadání, návrhu řešení a také testování. Samotné "//bušení//" do klávesnice přestane (by mělo) v tomto a následujících úkolech dominantní. Tím spíše, pokud se vaše "//psací//" dovednosti postupně zlepšují. 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". Pro řešení této úlohy (a to včetně bonusové části) vystačíte s polem. Pokud máte potřebu používat dynamickou alokaci, tak se ubíráte špatným směrem. Je dobré si uvědomit, že automatické proměnné jsou ukládány na zásobníku, který má zpravidla velikost 8MB. Pokud vám program končí chybou (např. segmentation fault ./a.out) je velmi pravděpodobné, že alokujete příliš mnoho paměti. Pro Eratosthenovo síto stáčí pole o velikosti 1M. Pokud bude mít prvek velikost 8 bytů, tak se již blížíte limitu. Velmi dobře lze přístup k paměti odladit programem [[http://valgrind.org/docs/manual/quick-start.html| valgrind]]. 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''. Pro testování funkčnosti program před jeho odevzdáním lze využít přiložené vstupní a referenční výstupní soubory. Dále je možné testovat také generátorem a referečním řešení viz [[courses:b0b36prp:tutorials:testing|Testování HW programů před odevzdáním]]. Pro generování volitelného zadání použijte dodatečný přepínač ''-optional''. Generování velkých náhodných čísel (pro bonusovou část) může trvat relativně dlouho, proto jsou při generování vypisovány na standardní chybový výstup znaky ''.'' indikující, že program pracuje. Generujte přímo do souboru s přesměrování např. ''./b0b36prp-hw04b-genref -generate >bonus_input-1.txt'' ==== Příklad 1 - pub01 ==== ^ 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 ==== ^ 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 ==== ^ 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 | ====== Povinné zadání ====== Na vstupu jsou pouze celá čísla menší než $10^8$, která jsou plně reprezentovatelná datovým typem 32-bitového ''​int''​. Na správné vyřešení v tomto případě postačí využít cykly a zpracovávat jednotlivá čísla jedno po druhém. Další datová struktura (pole) pro urychlení rozkladu na prvočísla není nutná. /*Při rozkladu vstpních čísel uvažujte pouze prvočísla menší než $10^6$.*/ ====== Volitelné zadání ====== Na vstupu jsou pouze celá čísla, která jsou reprezentovatelná pomocí 64-bitového celočíselného znamenkového datového typu. Vzhledem k náročnosti úkolu předpokládáme, že největší prvočí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. Proto je nutné uložit nalezená prvočísla do samostatného pole, aby nebylo potřeba vždy procházet celé Eratosthenovo síto. Doporučení: Pro uložení nalezených prvočísel používejte "pouze" 32-bitový celočíselný znamenkový typ. ==== Příklad 4 - pub04 ==== ^ 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 | ====== 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 ==== === Optional 01 === Přibližně 8000 čísel, které jsou většinou prvočísly z intervalu 2 až 100000. === Optional 02 === Přibližně 7000 čísel, které jsou většinou složené ze dvou prvočísel z intervalu 2 až 100000. === Optional 03 === Přibližně 300 čísel, které jsou většinou složené ze dvou prvočísel v intervalu 900000 až 1000000. ====== Bonusové zadání ====== 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 6 - pub06b ==== 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). Bonusové zadání má v odevzdávacím systému vlastní záložku HW04B. Bonusová část se po uplynutí termínu uzavře. Není proto nastavena žádná penalizace za pozdní odevzdání. /*Termín odevzdání byl posunut na **13.11.2016** 23:59 PDT. Použití vhodných datových typů může výrazně zrychlit váš program.*/ ====== Odevzdání ====== U tohoto domácího úkolu (jako jedinného) je linkována matematická knihovna **''math.h''** pomocí přepínače **''-lm''**. Neukládejte prvočísla přímo do zdrojového kódu, ​**maximální velikost souboru ''​main.c''​ je 50 kB**. Veřejné příklady + Makefile: {{:courses:b0b36prp:hw:b0b36prp-hw04.zip|}} ^ ^ Povinné zadání ^ Volitelné zadání ^ Bonusové zadání ^ ^ Název v BRUTE | HW04 || HW04B | ^ Odevzdávané soubory | main.c ||| ^ Argumenty při spuštění | žádné ||| ^ Návratová hodnota | ''0''; Program skončil úspěšně \\ ''100''; "Error: Chybny vstup!" -> ''stderr'' ||| ^ Kompilace pomocí | clang -pedantic -Wall -Werror -std=c99 -O3 -lm ||| ^ Velikost zásobníku | 8 MB ||| ^ Velikost haldy | //Dynamická alokace není potřeba// ||| ^ 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]]).)) | $\mathcal{O}(v)$ | $\approx \mathcal{O}\left(\dfrac{v}{\log{}v}\right)$ | $\approx \mathcal{O}\left(\dfrac{v}{\log{}v}\right)$ | ^ Procvičované oblasti | vnořené cykly | pole | pole |