Prvočísla

Prvočíslo je prirodzené číslo, ktoré je väčšie ako $1$ a ktorého jedinými deliteľmi sú $1$ a ono samo. Prirodzené čísla, ktoré nie sú prvočíslami sa s výnimkou čísla $1$ nazývajú zložené čísla. (wikipedia)

Na prvočísla občas natrafíme aj v programátorských úlohách. Často v nich potrebujeme overiť, či je nejaké číslo prvočíslom, prípadne nájsť všetky prvočísla v nejakom intervale (napr. v $[1,10^6]$).

Overovanie hľadaním deliteľov

Číslo $n>1$ je teda prvočíslo ak nemá v intervale $[2,n)$ žiadnych deliteľov. Úplne triviálny prístup je teda skúsiť všetky čísla v tomto intervale, a ak žiadne nenájdeme, potvrdíme že je to prvočíslo:

bool je_prvocislo(int n)
{
    for(int i=2;i<n;i++)
    {
        if(n % i == 0)
            return false;
    }
    return n>1;
}

V prípade, že je $n$ prvočíslo, však spravíme až $n-2 = O(n)$ krokov. Toto je príliš pomalé pre $n$ rádovo $10^9$, alebo viacero $n$ okolo $10^6$.

Tu prichádza na rad prvé dôležité pozorovanie. Povedzme, že $n$ nie je prvočíslo. Potom vieme $n$ zapísať ako $n = a \cdot b$, kde (BUNV $a \leq b$) platí $a \leq \sqrt n$. Ak by totiž $b \geq a > \sqrt n$, tak $a \cdot b > n$.

Inak sa na to dá pozerať aj tak, že každý deliteľ väčší rovný $\sqrt n$ má svoju dvojicu, ktorá je menšia rovná ako $\sqrt n $ (a naopak).

Vizualizácia pozorovania

Ak teda nenájdeme deliteľa čísla $n$ v intervale $[2, \sqrt n ]$, nemusíme ďalej hľadať - určite ho nemá ani v intervale $(\sqrt n ,n)$. Úplne jednoducho teda zrýchlime našu funkciu na overovanie prvočíslenosti - budeme hľadať len po odmocninu $n$.

bool je_prvocislo(int n)
{
    for(int i=2;i*i<=n;i++)
    {
        if(n % i == 0)
            return false;
    }
    return n>1;
}

V najhoršiom prípade teda spravíme $O(\sqrt n)$ operácií, ak je číslo prvočíslo alebo súčinom dvoch čísel blízko jeho odmocnine. To je slušné vylepšenie (z obrázku môžete vidieť, o koľko menej čísel overíme už pre relatívne malé $n = 77$); ak by sme takto skúsili overiť všetky čísla od $1$ po $n$ v snahe nájsť všetky prvočísla, zabralo by nám to $O(n \sqrt n) = O(n^{3/2})$ času. V praxi toto môže s rýchlym programovacím jazykom stačiť pre $n$ rádovo $10^6$.

Nasleduje tvrdenie, ktoré uvedemie bez dôkazu (je nad rámec tohto článku): dobrý odhad počtu prvočísel $\leq n$ je $\frac{n}{\log n}$, kde $\log$ označuje prirodzený logaritmus (so základom e ). Počet prvočísel $\leq n$ sa v matematike často označuje $\pi(n)$; toto budeme používať aj v našom článku, pričom $\pi(n) = O(\frac{n}{\log n})$.

Ďalšie vylepšenie môžeme teda spraviť pozorovaním, že ak $n$ je zložené číslo a teda má deliteľov, tak má zaručene aj prvočíselných deliteľov - nemusíme teda skúšať všetky čísla $\leq \sqrt n$, ale len všetky prvočísla $\leq \sqrt n$, ktorých je $\pi (\sqrt n)$. Samozrejme, toto urýchlenie overovania jednotlivých čísel prichádza s cenou - musíme si najprv predpočítať všetky dostatočne malé prvočísla. Toto sa oplatí, ak budeme chcieť overovať viacero čísel, alebo ak našim cieľom nájsť všetky prvočísla do $n$ - vtedy to sú predsa dve muchy jednou ranou.

vector<int> prvocisla;

void najdi_prvocisla(int n)
{
    for(int i=2;i<=n;i++)
    {
    bool ok = true;
        for(int j=0;j<prvocisla.size() && prvocisla[j]*prvocisla[j] <= i;++j)
        {
            if(i % prvocisla[j] == 0)
            {
                ok = false;
                break;
            }
        }

        if(ok)
        {
            prvocisla.push_back(i);
        }
    }
}

Tento prístup má teda časovú zložitosť $O(\frac{n \sqrt n}{\log \sqrt n})$, a pamäťovú $O(\frac{n}{\log n})$.

Ďalej