Úkol do IVT

Takže je na vstupu zadána řada n, x1, ... xn?

Pokud není třeba nějak optimalizovat, stačí každé číslo dělit v cyklu čísly 2 ... x/2 (většími čísly už zřejmě x v celých číslech nepodělíme). Pokud x modulo dělitel vyjde 0, pak x není prvočíslo. Při prvním podělení beze zbytku tedy vyskočit z cyklu a určit, že x není prvočíslem. Pokud x projde vším dělením, pak prvočíslem je. Na rozhodnutí stačí booleanová proměnná.

Sudá čísla vypadají hned na x mod 2. První optimalizací pak bude cyklus po lichých dělitelech, tedy od 3 se skokem 2. Zadaná čísla má navíc smysl dělit jen prvočísly, to by mohla být další optimalizace. A vymyslelo by se toho jistě víc, to už záleží na Vás.

Vlastně stačí dělitelé do x/3, x/2 dělí pouze sudá čísla a ta nepotřebujete. Vše mezi x/2 a x/3 pak zřejmě nepodělí x beze zbytku.

Také by se dalo např. rovnou dělit v cyklu 3 a x/3, 5 a x/5 ... dokud (dělitel <= x/dělitel). Taková optimalizace se snadno implementuje a výrazně sníží počet iterací cyklu.

Nuže v tom doplňku jsem to překombinoval a je to samozřejmě nesmysl, jde o to, že při troše přemýšlení stačí dělitelé do sqrt(x). ^^