Definice úlohy

Potřebujeme vytvořit přístroj, který odpoví na snadnou otázku ano či ne. Je dané celé číslo „n“ prvočíslem?
Zamysleme se nad tím, co by muselo být uvnitř, aby přístroj fungoval. Přístroje se řídí sekvencí kroků založené na nějakých instrukcích, což je známo jako algoritmus. Na rozehřání zjistěme, jaký je algoritmus v tvojí hlavě. Odpověz na následující otázku: Je 49 prvočíslo?
Ne? Jaký byl tvůj postup? Pravděpodobně hledat dělitele 49, který je větší než 1 a menší než 49. Pokud si nepamatuješ tabulku násobilky, postup byl asi následující:
  • Dělí 2 číslo 49?     NE
  • Dělí 3 číslo 49?     NE
  • Dělí 4 číslo 49?     NE
  • Dělí 5 číslo 49?     NE
  • Dělí 6 číslo 49?     NE
  • Dělí 7 číslo 49?    ANO!
Našli jsme dělitele čísla 49 (číslo 7), což je důkaz, že 49 není prvočíslo.

Stavění zdi

Co kdybychom se ale ptali, zda-li je 2 971 215 073 prvočíslo?
Ještě ověřuješ? Ani po prvních několika tisících testech jsem ještě nenašel dělitele. Klíčová otázka zní, kdy můžeme přestat ověřovat a dokázat, že „n“ je prvočíslo? (Nazvěme to naší zdí.) Jako výchozí bod víme, že naše zeď musí být „n-1“ (protože „n“ dělí „n“). Pokud bychom ověřovali do 2 971 215 072 buď bychom našli dělitele (což dokazuje, že „n“ není prvočíslo) nebo bychom jej nenašli (což dokazuje, že „n“ je prvočíslo).

Stavění lepší zdi

To by fungovalo, ale můžeme ale naší zeď posunout a ušetřit tím čas? Vzpomeň si, že hledáme prvního (nebo také nejmenšího) dělitele. Někdy může být nejmenším dělitelem 2, jindy zase něco většího. To nás přivádí k další klíčové otázce: Jak velký může být nejmenší dělitel?
Vzpomeň si, že každé „složené celé číslo n“ je tvořeno dvěma nebo více prvočísly „n= P * P…
P je největší, když má „n“ právě dva dělitele, které jsou si navzájem rovny. To je známo také jako druhá mocnina, jako například 9 (9 = 33) nebo 49 (49 = 77). Abychom zachytili tento nejhorší scénář, postavíme zeď na odmocnině z „n“!
Přesvědči se: Nenalezneme-li dělitele „n“ po testování až do odmocniny z „n“, pak musí být „n“ prvočíslo. Zkus to dokázat (důkaz bude na konci tohoto článku).

Algoritmus postupného dělení

A je to, jsme připraveni pokračovat. Nejdříve si náš algoritmus postupného dělení shrňme slovy:
  • Přijmi na vstupu celé číslo „n“
  • Pro každé celé číslo „x“ z {2, …, sqrt(n)} ověř, zda „x“ dělí „n“
  • Pokud najdeš dělitele, „n“ není prvočíslo, v opačném případě „n“ prvočíslem je.
Pokud máš zkušenosti s programováním, otevři si CS scratchpad a zkus takovou funkci zprovoznit. Pokud nemáš, můžeš pokračovat k dalšímu kroku, kde je poskytnuta funkční verze pro použití jako výchozí bod. (Pro tvou informace: Tuto lekci je možné zvládnout bez programování).
Načítám