Search
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.
Error: Chybny vstup!
100
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
12 -2 100 0
Prvociselny rozklad cisla 12 je: 2^2 x 3
12 b 100 0
991350783547 0
Prvociselny rozklad cisla 991350783547 je: 995663 x 995669
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.
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či2) 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*.
Vstupní číslo zkouší dělit všemi čísly menšími než je vstupní číslo.
Vstupní číslo zkouší dělit všemi menšími čísly. Algoritmus končí, když je dělenec menší než dělitel.
Využívá předpočítaná prvočísla do hodnoty $10^6$. Algoritmus končí, když je dělenec menší než dělitel.
main.c
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.
Rozkládané číslo5) je $(995663 * 995669)^8$:
932865073719992059629773513614789388266580305083920591925740371392254317064584855785088915745761 0
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).
<math.h>
-lm
Veřejné příklady + Makefile:b3b36prg-hw02.zip