Zjišťování prvočíselnosti
Naším úkolem je zjistit, zda zadané číslo je prvočíslo nebo číslo složené. Prvočíslo je takové přirozené číslo, které je beze zbytku dělitelné pouze 1 a sebou samým. Začátek posloupnosti prvočísel je 2, 3, 5, 7, 11, 13, 17, 19, 23, …1).
Algoritmus 1
Na základě výše uvedené definice budeme postupně zkoumat, zda zadané číslo2) cislo
je dělitelné 2, 3, 4, atd. až do cislo - 1
. Pokud takového dělitele nalezneme, jedná se o číslo složené, v opačném případě jde o prvočíslo. Program může být zapsán například takto:
- prvocislo1.py
# zjištění, zda zadané číslo je prvočíslo cislo = int(input('Zadej přirozené číslo: ')) # budeme testovat všechny možné dělitele # od 2 do zadaného čísla delitel = 2 # testování jednotlivých dělitelů v cyklu while delitel < cislo: if cislo % delitel == 0: # test dělitelnosti break # dělitel nalezen, není třeba dále testovat delitel = delitel + 1 # další dělitel # test a výpis výsledku if delitel == cislo: print(cislo, 'je prvočíslo') else: print(cislo, '=', delitel, '*', cislo // delitel, 'je číslo složené')
Zdá se, že náš program pracuje správně včetně okrajových případů, tj. hodnoty 2. Při zadání větších prvočísel (řekněme nad 1 000 000)3) je doba čekání na výsledek již znatelná a s růstem zadaného čísla se samozřejmě zvyšuje. Napadá nás tedy otázka, zda bychom nemohli náš algoritmus trochu vylepšit, aby byl rychlejší.
Algoritmus 2
Pokud si uvědomíme, že každé číslo dělitelné 4, 6, 8, 10, … je zároveň dělitelné i 2, pak téměř polovinu dělitelů můžeme přeskočit, protože dělitelnost 2 již byla dříve vyloučena. Nesmíme ale na začátku zapomenout na testování sudosti.
- prvocislo2.py
# zjištění, zda zadané číslo je prvočíslo cislo = int(input('Zadej přirozené číslo: ')) # budeme testovat dělitelnost 2 a pak všemi lichými # čísly od 3 do zadaného čísla delitel = 2 if cislo % delitel != 0: # pokud není sudé # testování lichých dělitelů delitel = 3 # testování jednotlivých dělitelů v cyklu while delitel < cislo: if cislo % delitel == 0: # test dělitelnosti break # dělitel nalezen, není třeba dále testovat delitel = delitel + 2 # další lichý dělitel # konec testování lichých dělitelů # test a výpis výsledku if delitel == cislo: print(cislo, 'je prvočíslo') else: print(cislo, '=', delitel, '*', cislo // delitel, 'je číslo složené')
Pro větší čísla je pokrok již znatelný. Mohli bychom jít ve zrychlování ještě dále?
Algoritmus 3
Ano, skutečně tu je poměrně jednoduchá cesta. Stačí si uvědomit skutečnost, že pokud nalezneme nějakého dělitele p čísla n, pak číslo q = n / p je také dělitelem n. Pokud jsou čísla p a q různá, pak právě jedno z nich je menší než odmocnina z n a druhé je větší než odmocnina z n4). Při jejich rovnosti platí n = p2.
Z toho vyplývá, že pokud otestujeme všechny možné dělitele až do odmocniny z n (včetně ), dále již testovat nemusíme. Pokud jsme nalezli dělitele, jedná se o číslo složené. Pokud ne, nemůže existovat žádný dělitel q větší než odmocnina z n, protože jsme nenalezli žádného dělitele p menšího než odmocnina z n, pro který by platilo p.q = n. To znamená, že n je prvočíslo. Takto můžeme rapidně omezit počet vykonávání cyklu s testem dělitelnosti.
- prvocislo3.py
# zjištění, zda zadané číslo je prvočíslo cislo = int(input('Zadej přirozené číslo: ')) # budeme testovat dělitelnost 2 a pak všemi lichými # čísly od 3 do odmocniny ze zadaného čísla (včetně) delitel = 2 if cislo % delitel != 0: # pokud není sudé # testování lichých dělitelů delitel = 3 # testování jednotlivých dělitelů v cyklu while delitel * delitel <= cislo: # POZOR: <= if cislo % delitel == 0: # test dělitelnosti break # dělitel nalezen, není třeba dále testovat delitel = delitel + 2 # další lichý dělitel # konec testování lichých dělitelů # test a výpis výsledku if delitel * delitel > cislo: # upravená podmínka print(cislo, 'je prvočíslo') else: print(cislo, '=', delitel, '*', cislo // delitel, 'je číslo složené')
Nárůst rychlosti běhu programu pro větší prvočísla je skutečně razantní, přestože jsme provedli jen drobnou úpravu zdrojového kódu.
Za povšimnutí stojí tvar použité podmínky delitel * delitel <= cislo
. Ten je výhodnější než podoba dělitel <= cislo ** 0.5
, protože celočíselné operace jsou obecně rychlejší a netrpí problémy s omezenou přesností typu float
.
Porovnání rychlosti
Je zřejmé, že pro rychlost vykonání algoritmu je zásadní počet opakování cyklu s testem dělitelnosti. Proto u srovnatelně velkých čísel bude nejdéle trvat testování těch, které mají pouze velké netriviální dělitele a úplně nejdéle u prvočísel.
Při hodnocení efektivity algoritmu se obvykle zajímáme o chování pro „velké“ zadání dané úlohy a snažíme se postihnout nárůst doby běhu (a případně i spotřeby paměti) v závislosti na nějakém parametru, který velikost úlohy charakterizuje. V tomto případě je takovým vhodným parametrem právě velikost zkoumaného čísla n a zkoumáme maximální dobu běhu programu (tedy pro prvočíselná n).
V případě algoritmu 1 je maximální počet opakování cyklu přibližně roven n5). V algoritmu 2 jsme vyloučili z testování sudá čísla (s výjimkou 2), tudíž můžeme maximální počet opakování cyklu odhadnout jako ½ n (tj. zrychlení je asi dvojnásobné). V algoritmu 3 testujeme jen dělitele do odmocniny z n a to ještě pouze liché6). Počet opakování cyklu bude nejvýše okolo ½.√n. Je však třeba také uvážit, že vyhodnocení podmínky cyklu je mírně náročnější než u předchozích algoritmů.
Pokud provedeme skutečné měření doby běhu programu pro nějaké větší prvočíslo, uvidíme dobrou shodu s naší předpovědí. Konkrétně pro ověření prvočíselnosti 164 511 353 na letitém notebooku bylo naměřeno:
Algoritmus | Doba běhu [s] | Vykonaných cyklů |
---|---|---|
1 | 62,95 | ∼164 000 000 |
2 | 31,99 | ∼82 000 000 |
3 | 0,0032 | ∼6 400 |
Poučení
Z výše uvedeného rozboru a provedeného měření plyne jednoznačný závěr. V první řadě je samozřejmě nutné, aby použitý algoritmus správně řešil zadanou úlohu. Pak je ale také potřeba zamyslet se nad tím, jak velké úlohy budeme v praxi programem řešit a jak rychle řešení požadujeme7). Případně je vhodné snažit se o vylepšení algoritmu. Mnohdy je jednodušší o trochu více přemýšlet než nakoupit rychlý superpočítač . Poznatky z matematiky nám často mohou významně pomoci. Na našem příkladě jsme viděli, že i u velmi jednoduchých algoritmů může malá úprava činit divy!