HW 3 - Prvočíselný rozklad

Termín odevzdání	06.04.2024@23:59 PDT
Povinné zadání	3b kontrola Coding stylu
Volitelné zadání	není
Bonusové zadání	5b - 24.05.2024@23:59 CEST
Počet uploadů	20
Výchozí soubory	bab36prga-hw3.zip bab36prga-hw3b.zip

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í.

V programu není potřeba dynamická alokace a lze vystačit s lokálními proměnnými na zásobníku, který je však omezen na 8 MB. Proto dekomponujte a implementujte funkci, která připravý prvočísla Eratosthenovým sítem a vyplní připravené pole prvočísel. Počet prvočísel menších než $1 000 000$ (1×10⁶) je méně než $100 000$ (1×10⁵), tj. méně než 400 kB, ale 1×10⁶ int hodnot je cca 3.8 MB.

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 znaménkové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 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ý znaménkový typ.

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 valgrind.

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¹⁾ 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 ²⁾	DNF ³⁾
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.

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 5 - pub01-b

Rozkládané číslo⁴⁾ 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 <math.h> a to přepínačem -lm.

	Povinné zadání	Bonusové zadání
Název v BRUTE	HW3	HW3B
Odevzdávané soubory	main.c, *.h ⁵⁾
Argumenty při spuštění	žádné	žádné
Kompilace pomocí	clang -pedantic -Wall -Werror -std=c99 -O3 -lm
Očekávaná časová složitost⁶⁾	$\approx \mathcal{O}\left(\dfrac{v}{\log{}v}\right)$	$\approx \mathcal{O}\left(\dfrac{v}{\log{}v}\right)$
Procvičované oblasti	pole	pole

¹⁾

Notebook, Intel Core i5 CPU M480 @ 2.67 GHz, 8GB RAM DDR3 1066 MHz.

²⁾ , ³⁾

Více než 10 minut.

⁴⁾

Je možné si ověřit na Wolfram Alpha - výpočet.

⁵⁾

Jeden soubor main.c může používat více hlavičkových souborů. Nevytvářejte žádné složky.

⁶⁾

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$ (Prime number).

Table of Contents