Прости бројеви¶

Подсетимо се да у програмима операција % представља остатак при дељењу. Када желимо да проверимо да ли је број n дељив бројем d, проверавамо да ли је n % d == 0. Оваква провера ће се редовно појављивати у програмима који следе.

Као што знамо, природан број је прост ако је дељив само бројем 1 и самим собом. То значи да тест прималности броја n (проверу да ли је број n прост) можемо да обавимо тако што за сваки број од 2 до n-1 проверимо да ли је n дељив тим бројем. Ако n није дељив ни једним од тих бројева, то значи да је прост. Овакво проверавање ради за све бројеве осим за број 1, па тај случај разматрамо посебно.

Препознајете операцију претраживања - тражимо делилац броја n. Ако га нађемо, број је сложен, у противном је прост.

Тестирајте програм и уверите се да исправно ради. Испробајте га и за неке велике бројеве, на пример \(n = 1~000~000~000\). Приметићете да на одговор треба сачекати. То није ништа чудно, јер програм обавља скоро милијарду провера. Питање је да ли је било неопходно да се обави толико провера.

Једна ствар коју можемо да учинимо да бисмо смањили број операција је да прекинемо петљу чим нађемо један делилац, јер тада већ знамо одговор. Тако, уместо

if (n % i == 0)
    prost = false;

можемо да пишемо

if (n % i == 0)
{
    prost = false;
    break;
}

Програм сада ради много брже за \(n = 1~000~000~000\). То је наравно зато што је ово n дељиво са 2, а то значи да из петље излазимо већ у првој итерацији. Чак и да број није дељив баш са 2, број провера ће бити много мањи него у првој верзији. Често, али не увек. Испробајте измењен програм за \(n = 1~000~000~007\). Програм се поново дуго извршава. То је зато што је овај број прост, па нам наредба break ништа не помаже. Тело петље се поново извршава око милијарду пута. Можемо ли још нешто да учинимо?

Приметимо да ако је број n сложен, не могу сви његови делиоци бити већи од \(\sqrt{n}\). Заиста, када би то било могуће, онда би за било који делилац d броја n бројеви d и n/d оба били делиоци од n који су већи од \(\sqrt{n}\), па би њихов производ морао да буде већи од \(\sqrt{n} \cdot \sqrt{n} = n\), али \(d \cdot n/d = n\), то јест није веће од n, што је контрадикција!

Ово значи да број n, ако је сложен, мора имати делилац који је мањи или једнак \(\sqrt{n}\). Другим речима, ако број n који је већи од 2 нема делилац мањи или једнак од \(\sqrt{n}\), онда је тај број прост.

Захваљујући овом разматрању, број итерација можемо значајно да смањимо. Проверe дељивости са i могу да почну са i=2, а да се прекину када је \(i \cdot i > n\) (ако до тада није нађен делилац онда га и нема).

Сада, чак и за \(n = 1~000~000~007\) програм даје резултат без застоја. То смо и очекивали, јер број операција је овај пут приближно \(\sqrt{1~000~000~007} < 32~000\). Дакле, програм је сада пар десетина хиљада пута бржи!

Програм се може и даље убрзавати, али не више овако драстично. На пример, можемо да искористимо чињеницу да је број 2 једини паран прост број, па према томе и једини паран број за који треба проверити да ли је делилац од n (ако n није дељив са 2, онда није дељив ни једним парним бројем). Зато можемо проверу дељивости са 2 да обавимо пре петље, а у петљи да почнемо од 3 па да повећавамо i за по 2, проверавајући на тај начин само непарне i. Тиме би програм постао још двоструко бржи.

Даља убрзавања програма би била све мања, а овде нам и нису од значаја, па ћемо се на овоме зауставити.

Покушајте да решите задатке на тему дељивости, који следе у наставку.