Одређивање свих простих бројева до дате границе¶

Нека су нам потребни сви прости бројеви мањи од \(10~000~000\). Један начин да одредимо све просте бројеве у датим границама је да за сваки од њих појединачно проверимо да ли је прост, не користећи информације о осталим простим бројевима. Раније смо видели да провера да ли је број \(K\) прост захтева око \(\sqrt K\) операција. Зато је број операција потребан за проверу прималности сваког од првих \(N\) бројева појединачно, сразмеран са \(N \sqrt N\).

Доказ: Доказаћемо да за неке позитивне реалне константе \(c_1, c_2\) важи

\[c_1 N \sqrt {N} \leq \sum\limits_{K=1}^N \sqrt{K} \leq c_2 N \sqrt {N}\]

Друга неједнакост се лако доказује:

\[\begin{split}\begin{aligned} \sum\limits_{K=1}^N \sqrt{K} &= \sqrt 1 + \sqrt 2 + \sqrt 3 + \ldots + \sqrt N\\ &\leq \sqrt N + \sqrt N + \sqrt N + \ldots + \sqrt N\\ &= N \sqrt {N}\\ &= c_2 N \sqrt {N}\\ \end{aligned}\end{split}\]

где је \(c_2 = 1\). Ради доказа прве неједнакости, претпоставимо да је \(N\) паран број. Тада важи

\[\begin{split}\begin{aligned} \sum_{K=1}^N \sqrt{K} &= \sqrt 1 + \sqrt 2 + \sqrt 3 + \ldots + \sqrt N\\ &\geq \sqrt {\frac{N}{2}+1} + \sqrt {\frac{N}{2}+2} + \ldots + \sqrt N \\ &\geq \sqrt {\frac{N}{2}} + \sqrt {\frac{N}{2}} + \ldots + \sqrt {\frac{N}{2}} \\ &= \frac{N}{2} \sqrt {\frac{N}{2}}\\ &= \frac{1}{2 \sqrt 2} N \sqrt {N}\\ &= c_1 N \sqrt {N}\\ \end{aligned}\end{split}\]

где је \(c_1 = \frac{1}{2 \sqrt 2}\). Врло сличне неједнакости могу да се изведу и за непрарно \(N\). Дакле, важи

\[c_1 N \sqrt {N} \leq \sum\limits_{K=1}^N \sqrt{K} \leq c_2 N \sqrt {N}\]

Јасно је да при провери да ли је дати број \(\sqrt K\) прост, информација о мањим, претходно одређеним простим бројевима може да уштеди време. Постоје разни начини да ову информацију искористимо. Један веома једноставан, а истовремено веома ефикасан начин је да сваки прост број који откријемо, одмах искористимо да све његове умношке означимо као сложене.

Поступак би текао овако:

упишемо све бројеве од \(1\) до \(N\) у табелу. На почетку ниједан број није прецртан
за сваки број \(K\) почевши од \(K=2\) до \(K=N\), радимо следеће:
- ако је број \(K\) прецртан, значи да је сложен и прелазимо на следеће \(K\)
- ако број \(K\) није прецртан, значи да је прост. Искористимо га да прецртамо све бројеве облика \(K \cdot M\) до краја табеле, где је \(M\) природан број.

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

Описани поступак налажења простих бројева у ствари налази сложене бројеве и избацује их из колекције. По томе поступак подсећа на просејавање, где кроз сито пропада све што нас не интересује, а на крају у ситу остаје оно што смо тражили. Зато је овај поступак познат као Ератостеново сито, по грчком математичару Ератостену који га је описао.

Приметимо још да за просто \(K\) прецртавање можемо да почнемо од \(K^2\), јер су сложени бројеви између \(K\) и \(K^2\) већ прецртани користећи неке њихове мање делиоце. Из истог разлога, довољно је да \(K\) иде само до \(\sqrt N\), јер су сложени бројеви од \(\sqrt N\) до \(N\) прецртани већ наиласком на њихов први нетривијалан делилац, који мора бити мањи или једнак \(\sqrt N\).

Овако оптимизован поступак може да се илуструје следећим корацима:

❮

❯

Видимо да је за бројеве до 100 довољно да се за прецртавање искористе само прва 4 проста броја.

Ево и имплементације Ератостеновог сита у облику C# програма:

Број операција у овом алгоритму сразмеран је броју прецртавања, а он је једнак \(n/2 + n/3 + n/5 + n/7 + n/11 + ... + n/p\), где је \(p\) највећи прост број мањи или једнак \(\sqrt n\). Овде се нећемо упуштати у израчунавање процене вредности овог збира, али напомињемо да она расте тек незнатно брже од \(n\), тачније, расте брзином \(n \log {\log n}\). Ова брзина повећавања броја операција се за практичне потребе може сматрати равноправном са линеарном, јер за \(n \leq 2^{64}\) важи \(\log {\log n} \leq \log {64} = 6\).

Модификације Ератостеновог сита¶

У оригиналном алгоритму Ератостеновог сита користимо низ логичких вредности, у коме вредност true одговара непрецртаним бројевима, а вредност false прецртаним. Ако бисмо уместо низа логичких, користили низ целобројних вредности, онда приликом одређивања простих и сложених бројева можемо да запамтимо и неке додатне информације о сложеним бројевима, на основу којих могу да се убрзају неки будући поступци над њима. У наставку ћемо показати две модификације Ератостеновог сита, које омогућавају знатно ефикасније решавање разних проблема.

Памћење броја простих бројева мањих од датог¶

Најједноставнија модификација је да за сито користимо низ \(p\) целих бројева, у коме на позицијама простих бројева пишемо 1, а на осталим позицијама 0. Низ \(p\) називамо низом индикатора простих бројева. Описана модификација не носи ништа више информација него логички низ и сама за себе није нарочито корисна. Међутим, помоћу низа индикатора лако можемо да израчунамо кориснији низ \(s\), у коме је \(s_i\) број простих бројева из интервала \([1, i]\). Довољно је да уочимо да важи \(s_i = s_{i-1} + p_i\) да бисмо низ \(s\) израчунали у једном пролазу кроз низ индикатора. За низ \(s\) можемо чак да користимо исти простор, тј. низ \(p\), јер нам након рачунања \(s_i\) неће више бити потребан индикатор \(p_i\), тако да можемо да га „прегазимо”.

Када израчунамо низ \(s\), можемо да га искористимо за брзо одређивање броја простих бројева у било ком интервалу \([a, b]\) као \(s_b - s_{a-1}\). Све ово је илустровано у следећем програму. Приликом покретања програма потребно је најпре унети величину сита \(n\), а затим парове бројева \(a, b\), који представљају границе интервала који нас интересују (\(a \leq b\)). Програм се завршава уносом нуле за вредност \(b\).

Памћење најмањег делиоца сваког броја¶

Погледајмо следећу модификацију Ератостеновог сита:

У функцији NajmanjiDelilac формира се низ delilac, који на позицији i садржи најмањи нетривијалан делилац броја i. И овај поступак је врло сличан оригиналном Ератостеновом ситу, тако да га нећемо посебно објашњавати.

Као прву, најједноставнију илустрацију новодобијених могућности, поменимо да захваљујући направљеној модификацији Ератостеновог сита, сада било који број мањи или једнак \(n\) можемо да раставимо на просте чиниоце, без икаквог додатног рачунања (довољно је приступање елементима низа, које се обавља веома ефикасно). Управо ова могућност је већ илустрована у функцији Main претходног програма.

Показаћемо још једну, нешто напреднију могућност употребе овако модификованог Ератостеновог сита, а то је веома ефикасно одређивање броја делилаца било ког датог броја, мањег или једнаког \(n\).

На основу основне теореме алгебре знамо да за сваки природан број \(x\) постоји јединствени растав тог броја на просте чиниоце, \(x = p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} \cdot ... \cdot p_k ^ {\alpha_k}\), где су \(p_1, p_2, ... p_k\) сви прости бројеви којима је број \(x\) дељив. Користећи ово, сваки делилац \(d\) броја \(x\) можемо да запишемо у облику \(d = p_1 ^ {\beta_1} \cdot p_2 ^ {\beta_2} \cdot ... \cdot p_k ^ {\beta_k}\), где је \(0 \leq \beta_1 \leq \alpha_1, 0 \leq \beta_2 \leq \alpha_2, ... 0 \leq \beta_k \leq \alpha_k\). Према томе, сваки делилац \(d\) броја \(x\) одређен је k-торком бројева \((\beta_1, \beta_2, ... \beta_k)\), па је број делилаца броја \(x\) (укључујући 1 и \(x\)) једнак броју оваквих k-торки. Како за \(\beta_i\) постоји \(\alpha_i + 1\) различитих могућих вредности од 0 до \(\alpha_i\) (\(1 \leq i \leq k\)), то је број могућих k-торки, а тиме и број делилаца броја \(x\) једнак \((\alpha_1 + 1) \cdot (\alpha_2 + 1) \cdot ... \cdot (\alpha_k + 1)\).

Примери:

\(16 = 2^4\), па је број делилаца броја 16 једнак \((4+1) = 5\). Заиста, делиоци броја 16 су бројеви 1, 2, 4,8 и 16.
\(24 = 2^3 \cdot 3^1\), па је број делилаца броја 24 једнак \((3+1) \cdot (1+1) = 8\) (то су бројеви 1, 2, 3, 4, 6, 8, 12, 24).
\(36 = 2^2 \cdot 3^2\), па је број делилаца броја 36 једнак \((2+1) \cdot (2+1) = 9\) (то су бројеви 1, 2, 3, 4, 6, 9, 12, 18, 36).

Када је за сваки број унапред познат његов најмањи нетривијалан делилац, број делилаца броја \(x\) може по овој формули да се одреди уз веома мало рачунања. Следећи програм показује како то може да се уради.

Начини да употребимо модификовано Ератостеново сито се ни изблиза овим не исцрпљују. Примера ради, и збир делилаца датог природног броја може да се одреди користећи разматрање слично претходном. Покажимо ово на примеру \(x = 72\). Овај број има \(3 \cdot 4 = 12\) делилаца, а то су 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72. При рачунању њиховог збира можемо груписањем сабирака да формирамо неколико геометријских прогресија:

\[\begin{split}\begin{aligned} s &= 1 + 2 + 3 + 4 + 6 + 8 + 9 + 12 + 18 + 24 + 36 + 72\\ &= (1 + 2 + 4 + 8) + (3 + 6 + 12 + 24) + (9 + 18 + 36 + 72)\\ &= (1 + 2 + 4 + 8) + 3(1 + 2 + 4 + 8) + 9(1 + 2 + 4 + 8)\\ &= (1 + 2 + 4 + 8) \cdot (1 + 3 + 9)\\ &= \frac{16-1}{2-1} \cdot \frac{27-1}{3-1}\\ &= \frac{15}{1} \cdot \frac{26}{2}\\ &= 15 \cdot 13\\ &= 195\\ \end{aligned}\end{split}\]

У извођењу смо на два места искористили формулу \(1 + p + p^2 + ... + p^k = \frac{p^{k+1}-1}{p-1}\) за збир геометријске прогресије.

Уопштавањем овог поступка можемо да дођемо до формуле за општи случај, у коме је \(x = p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} \cdot ... \cdot p_k ^ {\alpha_k}\). Већ смо констатовали да је сваки делилац \(d\) броја \(x\) облика \(d = p_1 ^ {\beta_1} \cdot p_2 ^ {\beta_2} \cdot ... \cdot p_k ^ {\beta_k}\), при чему је \(0 \leq \beta_1 \leq \alpha_1, 0 \leq \beta_2 \leq \alpha_2, \ldots, 0 \leq \beta_k \leq \alpha_k\). Према томе, збир \(s\) свих делилаца броја \(x\) је збир свих бројева облика \(p_1 ^ {\beta_1} \cdot p_2 ^ {\beta_2} \cdot ... \cdot p_k ^ {\beta_k}\) за разне вредности \(\beta_1, \beta_2, \ldots, \beta_k\). Груписањем и применом дистрибутивног закона, долазимо до тога да збир \(s\) може да се изрази овако:

\[\begin{split}\begin{aligned} s &= (1 + p_1 + p_1^2 + ... + p_1^{\alpha_1}) \cdot (1 + p_2 + p_2^2 + ... + p_2^{\alpha_2}) \cdot ... \cdot (1 + p_k + p_k^2 + ... + p_k^{\alpha_k})\\ &= \frac{p_1^{\alpha_1+1}-1}{p_1-1} \cdot \frac{p_2^{\alpha_2+1}-1}{p_2-1} \cdot ... \cdot \frac{p_k^{\alpha_k+1}-1}{p_k-1}\\ \end{aligned}\end{split}\]

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

Погледајмо још један пример. Нека је \(x = 60\). Пошто је \(60=2^2 \cdot 3^1 \cdot 5^1\), то је сваки делилац броја \(60\) облика \(d=2^{\beta_1} \cdot 3^{\beta_2} \cdot 5^{\beta_3}\), где је \(0 \leq \beta_1 \leq 2, 0 \leq \beta_2 \leq 1, 0 \leq \beta_3 \leq 1\). Дакле, збир свих делилаца броја \(60\) је

\[\begin{split}\begin{aligned} s &= 2^0 3^0 5^0 + 2^1 3^0 5^0 + 2^2 3^0 5^0 + 2^0 3^1 5^0 + 2^1 3^1 5^0 + 2^2 3^1 5^0\\ &+ 2^0 3^0 5^1 + 2^1 3^0 5^1 + 2^2 3^0 5^1 + 2^0 3^1 5^1 + 2^1 3^1 5^1 + 2^2 3^1 5^1\\ &= (2^0 3^0 + 2^1 3^0 + 2^2 3^0 + 2^0 3^1 + 2^1 3^1 + 2^2 3^1) 5^0 + (2^0 3^0 + 2^1 3^0 + 2^2 3^0 + 2^0 3^1 + 2^1 3^1 + 2^2 3^1) 5^1\\ &= (2^0 3^0 + 2^1 3^0 + 2^2 3^0 + 2^0 3^1 + 2^1 3^1 + 2^2 3^1) (5^0 + 5^1)\\ &= ((2^0 + 2^1 + 2^2) 3^0 + (2^0 + 2^1 + 2^2) 3^1) (5^0 + 5^1)\\ &= (2^0 + 2^1 + 2^2) (3^0 + 3^1) (5^0 + 5^1)\\ &= \frac{2^3-1}{2-1} \cdot \frac{3^2-1}{3-1} \cdot \frac{5^2-1}{5-1}\\ &= \frac{7}{1} \cdot \frac{8}{2} \cdot \frac{24}{4}\\ &= 7 \cdot 4 \cdot 6\\ &= 168\\ \end{aligned}\end{split}\]

Рачунање збира свих делилаца датог броја применом изведене формуле захтева знатно мање корака него што је потребно већ и за само генерисање или проналажење свих тих делилаца. Следећи програм то ради користећи претходно изведену формулу и модификовано Ератостеново сито.

Садржај

1. Основни алгебарски алгоритми

2. Основни геометријски алгоритми

3. Основни алгоритми текста

4. Основни графовски алгоритми

5. Одабрани алгоритми и структуре података

Одређивање свих простих бројева до дате границе¶

Модификације Ератостеновог сита¶

Памћење броја простих бројева мањих од датог¶

Памћење најмањег делиоца сваког броја¶