Prvočísla

8. ročník | 2019/2020 | 2. kolo | Európa a Ázia
Kategória A | Autor | Ing. Mgr. Martin Hriňák

Maximálny počet bodov: 10


Prvočísla sú také prirodzené čísla, ktoré majú práve dvoch rôznych prirodzených deliteľov – jednotku a samého seba. Jednou z možností, ako zistiť, že dané číslo je prvočíslo, je vyskúšať, či nie je deliteľné všetkými prirodzenými číslami menšími ako je ono samo. Druhou možnosťou je skúšať prirodzené čísla po odmocninu z tohto prirodzeného čísla. 

Inou možnosťou je tzv. Eratostenovo sito, metóda pomenovaná podľa gréckeho matematika Eratostena. Napíšme si čísla od 1 po n do tabuľky. Na obrázku vidíte situáciu pre n = 120. Ako prvé vyškrtneme číslo 1, pretože nie je prvočíslom. Potom zakrúžkujeme najmenšie nevyčiarknuté číslo – 2 (označená tmavočervenou farbou na obrázku). Potom vyčiarkneme z tabuľky všetky jeho prirodzené násobky (4, 6, 8... – vyznačené svetločervenou farbou). Potom zakrúžkujeme opäť najmenšie nevyčiarknuté číslo – 3 (tmavozelená farba) a vyčiarkneme jeho násobky (svetlozelená farba, ak už niektorý z týchto násobkov bol vyčiarknutý, tak zostane vyčiarnutý). Potom zakrúžkujeme opäť najmenšie nevyčiarknuté číslo – 5 (tmavomodrá) a vyčiarneme jeho násobky (svetlomodrá). 

Takto postupujeme dovtedy, kým tabuľka nebude obsahovať buď vyčiarknuté, alebo zakrúžkované čísla. Zakrúžkované čísla budú predstavovať všetky prvočísla v danom číselnom rozsahu.

a)    Dokáž, že táto metóda nájde všetky prvočísla v danom číselnom intervale.

b)    Dokáž, že každé prvočíslo väčšie ako 3 sa dá vyjadriť v tvare 6k ± 1, kde k je prirodzené číslo.

Animovanú verziu tohto obrázka nájdeš na https://LaBaK.net.


Prílohy

attach_fileSúbor k úlohe | obrazok.gif


Diskusia

lock

Odosielanie riešení

Máš vyriešenú úlohu? Zaregistruj sa alebo prihlás sa do svojho konta pre odoslanie riešenia úlohy.