Uživatelské nástroje

Nástroje pro tento web


prog:prvocislo

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!

1)
1 za prvočíslo nepovažujeme, jediným sudým prvočíslem je 2.
2)
zde i v následujícím textu budeme předpokládat přirozené číslo ≥ 2
3)
můžete vyzkoušet např. 3 033 169, 7 530 161, 15 790 321, 22 366 891
4)
rozmyslete si, proč
5)
pro dostatečně velká n je rozdíl mezi n a n - 2 prakticky zanedbatelný
6)
samozřejmě také 2
7)
Pokud budeme kupříkladu řešit předpověď počasí na další den a výpočet bude trvat týden, je výsledek prakticky bezcenný.
prog/prvocislo.txt · Poslední úprava: 31.10.2017 07:32 autor: Ivana Stefanová