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, …¹⁾.

Na základě výše uvedené definice budeme postupně zkoumat, zda zadané číslo²⁾ 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)³⁾ 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ší.

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?

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 n⁴⁾. Při jejich rovnosti platí n = p².

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.

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 n⁵⁾. 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é⁶⁾. 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

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žadujeme⁷⁾. 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!