Тест прималности¶

Подсетимо се најпре дефиниције простог броја:

Дефиниција:

Природан број \(n > 1\) је прост, ако су \(1\) и \(n\) његови једини делиоци.

Природан број \(n > 1\) је сложен, ако он, осим \(1\) и \(n\), има и других делилаца (већих од \(1\), а мањих од \(n\)).

На основу дате дефиниције закључујемо да је сваки природан број осим јединице или прост или сложен. При томе, за било који довољно мали природан број лако можемо напамет да проверимо да ли је он прост. На пример, број 29 је прост, јер он није дељив ни са једним од бројева од 2 до 28. Са друге стране, број 49 је сложен јер је дељив са 7. За дати број \(n\), његове делиоце \(1\) и \(n\) називамо тривијалним делиоцима, а остале нетривијалним (ако их има). Тако можемо да кажемо да је прост број онај који има само тривијалне делиоце, а сложен онај који има и бар један нетривијалан делилац.

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

Задатак – да ли је број прост: За дати цео број \(n\) проверити да ли је прост (исписати DA ако јесте, а NE ако није).

Формулисаћемо први поступак директно на основу дефиниције простог броја. Проверу да ли је број \(n\) прост обавићемо тако што за сваки број \(i\) од \(2\) до \(n-1\) проверимо да ли је \(n\) дељив бројем \(i\). Ако \(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 > \sqrt{n}\) (ако до тада није нађен нетривијалан делилац, онда га и нема).

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

Приметимо да овај програм чак и за \(n = 1~111~111~111~111~111~111\) даје одговор да је број прост у року од свега неколико секунди, док би почетној верзији програма за ово било потребно много више времена.

Q-1: Претпоставимо да је првој верзији програма потребно 6 секунди да дође до одговора за \(n = 1~000~000~007\). Колико времена би истом програму било потребно да одговори за \(n = 1~111~111~111~111~111~111\)?

Процените време користећи чињеницу да су оба броја проста и да је, према томе, у оба случаја број провера приближно једнак \(n\).

• неколико сати
• неколико дана
• неколико година
• неколико стотина година
• неколико милијарди година

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

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

Задатак:

Проучите следећу, четврту верзију програма.

Објасните због чега је ово решење такође коректно.

Одредите за које бројеве програм проверава да ли су делиоци од n у случају да је n=101.

Процените однос брзина последње две верзије програма за велике вредности n.

Q-2: Нека је претпоследњој (трећој) верзији програма потребно време \(t\) да одговори на питање за дато \(n\). Колико је времена приближно потребно последњој, четвртој верзији програма за исто \(n\)?

• sqrt(t)
• t/2
• t/3
• 2t/3
• 3t/4