Очигледан алгоритам за одређивање свих простих бројева из неког интервала јесте да се за сваки број из тог интервала појединачно провери да ли је прост. Ово може бити урађено уз помоћ алгоритма тј. функције коју смо описали у задатку Прост број.
На основу спецификације задатка потребно је одредити највише 6 последњих цифара збира свих простих бројева из интервала \([a, b]\), што, је еквивалентно одређивању збира тих бројева по модулу \(10^6\). Наиме, важи \((a + b) \,\mathrm{mod}\,m = (a \,\mathrm{mod}\,m + b \,\mathrm{mod}\,m) \,\mathrm{mod}\,m\). У петљи пролазимо кроз све бројеве од \(a\) до \(b\), вршимо филтрирање на основу услова да је број прост и вршимо бројање и сабирање добијене филтриране серије.
Напоменимо да се збир рачуна тако што се на почетку иницијализује на нулу, а затим се у сваком кораку израчунава сабирање збира и текућег простог броја по модулу \(10^6\) (zbir = (zbir % 1000000 + p % 100000) % 100000). Пошто ће у сваком кораку збир бити мањи од \(10^6\), и пошто не постоји опасност од прекорачења када се у обзир узме максимална вредност простих бројева који се сабирају, претходни корак се може заменити кораком zbir = (zbir + p) % 1000000.
#include <iostream>
#include <vector>
using namespace std;
// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
if (n == 1) return false; // broj 1 nije prost
if (n == 2) return true; // broj 2 jeste prost
if (n % 2 == 0) return false; // ostali parni brojevi nisu prosti
// proveravamo neparne delioce od 3 do korena iz n
for (int i = 3; i*i <= n; i += 2)
if (n % i == 0)
return false;
// nismo nasli delioca - broj jeste prost
return true;
}
// funkcija odredjuje broj i zbir po modulu 1000000 prostih brojeva iz
// intervala [a, b]
void prostiUIntevalu(int a, int b, int& broj, int& zbir) {
zbir = 0, broj = 0;
for (int i = a; i <= b; i++)
if (prost(i)) {
zbir = (zbir + i) % 1000000;
broj++;
}
}
int main() {
// ucitavamo granice intervala
int a, b;
cin >> a >> b;
// odredjujemo broj i zbir po modulu 1000000 prostih brojeva iz
// intervala [a, b]
int broj, zbir;
prostiUIntevalu(a, b, broj, zbir);
// prijavljujemo rezultat
cout << broj << " " << zbir << endl;
return 0;
}Сложеност. Ако се провера да ли је дати број \(k\) прост врши у сложености \(O(\sqrt{k})\), тада је овај алгоритам сложености \(O((b-a) \sqrt{b})\). Ако је интервал облика \([0, n]\), сложеност је \(O(n\sqrt{n})\).
Бољи резултат од испитивања за сваки број појединачно да ли је прост може се добити применом алгоритма познатог као Ератостеново сито. Основна идеја алгоритма је да се прво напишу сви бројеви од 1 до датог броја \(n\), затим да се прецрта број 1 (јер он по дефиницији није прост), након њега сви умношци броја 2 (нису прости зато што су дељиви са 2, док број 2 остаје непрецртан јер је он прост), затим умношци броја 3 (нису прости јер су дељиви бројем 3), затим умношци броја 5 (нису прости зато што су дељиви бројем 5) и тако даље.
Ефикасна имплементација овог алгоритма подразумева неколико одсецања (којима се избегава понављање истих операција више пута и асимптотски убрзава алгоритам).
Прво, умношке сложених бројева нема потребе посебно прецртавати јер су они већ прецртани током прецртавања умножака неког од њихових простих фактора (на пример, нема потребе посебно прецртавати умношке броја 4 јер су они већ прецртани током прецртавања умножака броја 2).
Друго, приликом прецртавања умножака броја \(d\) довољно је кренути од \(d\cdot d\) јер су мањи умношци већ прецртани раније (сви имају праве факторе мање од \(d\)). Зато је потребно је да се поступак понавља само док се не прецртају умношци свих простих бројева који (прости бројеви, а не умношци) нису већи од корена броја \(n\). За бројеве веће од корена од \(n\) прецртавање би кренуло од њиховог квадрата који је већи од \(n\), па је јасно да се ни за један од њих ништа додатно не би прецртало.
Бројеви који су остали непрецртани су прости (јер знамо да немају правих делилаца мањих или једнаких корену од \(n\), па самим тим и мањих или једнаких свом корену, а пошто немају делилаца испод вредности корена, немају правих делилаца ни изнад вредности корена). Та теорема је доказана у задатку Прост број.
Пример. Прикажимо како се овим алгоритмом одређују сви прости бројеви од 2 до 50. Крећемо од пуне табеле у којој су уписани сви бројеви од 2 до 50.
. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
У првом кораку прецртавамо све умношке броја 2 (осим самог броја 2).
. 2 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25 . 27 . 29 . 31 . 33 . 35 . 37 . 39 . 41 . 43 . 45 . 47 . 49 .
У наредном кораку прецртавамо све умношке броја \(3\), кренувши од његовог квадрата тј. од \(9\) (број \(6\) је већ прецртан као умножак броја \(2\)).
. 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . 25 . . . 29 . 31 . . . 35 . 37 . . . 41 . 43 . . . 47 . 49 .
Умношке броја \(4\) не прецртавамо, јер је он прецртан (па самим тим и сви његови умношци).
У наредном кораку прецртавамо све умношке броја \(5\), кренувши од његовог квадрата тј. броја \(25\) (умношци \(2\cdot 5\), \(3\cdot 5\) и \(4\cdot 5\) су већ прецртани).
. 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 . 31 . . . . . 37 . . . 41 . 43 . . . 47 . 49 .
Умношке броја \(6\) не прецртавамо, јер је он прецртан (па самим тим и сви његови умношци).
Прецртавамо умношке броја \(7\), кренувши од његовог квадрата тј. броја \(49\).
. 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 . 31 . . . . . 37 . . . 41 . 43 . . . 47 . . .
Умношке броја \(8\) не прецртавамо, јер је он прецртан (па самим тим и сви његови умношци). Међутим, прецртавање би кренуло од његовог квадрата. И за све наредне бројеве прецртавање креће од њиховог квадрата, међутим, тај квадрат је већ ван табеле (јер је већи од 50), па се поступак може завршити. Преостали бројеви су прости.
Прецртавање бројева моделоваћемо низом (или вектором) који садржи логичке вредности (вредности типа bool) и прецртане бројеве означаваћемо са false, а непрецртане са true. Одређивање простих бројева (помоћу поменутог низа тј. вектора) реализоваћемо у засебној функцији, јер та функција може бити корисна и у многим наредним задацима.
Рецимо и да је без обзира на то што су нама потребни само бројеви из интервала од \(a\) до \(b\), у Ератостеновом ситу потребно вршити анализу свих бројева из интервала од \(0\) до \(b\) (јер се прецртавање мора вршити и бројевима мањим од \(a\)).
#include <iostream>
#include <vector>
using namespace std;
// funkcija koja popunjava logicki niz podacima o prostim brojevima iz
// intervala [0, n]
void Eratosten(vector<bool>& prost, int n) {
// alociramo potreban prostor
prost.resize(n + 1, true);
prost[0] = prost[1] = false; // 0 i 1 po definiciji nisu prosti
// brojevi ciji se umnosci precrtavaju
for (int i = 2; i * i <= n; i++)
// nema potrebe precrtavati umnoske slozenih brojeva
if (prost[i]) {
// precrtavamo umnoske broja i i to krenuvsi od i*i
for (int j = i * i; j <= n; j += i)
prost[j] = false;
}
}
// funkcija odredjuje broj i zbir po modulu 1000000 prostih brojeva iz
// intervala [a, b]
void prostiUIntevalu(int a, int b, int& broj, int& zbir) {
// odredjujemo proste brojeve u intervalu [0, b]
vector<bool> prost;
Eratosten(prost, b);
// analiziramo jedan po jedan broj u intervalu
zbir = 0; broj = 0;
for (int i = a; i <= b; i++)
if (prost[i]) {
zbir = (zbir + i) % 1000000;
broj++;
}
}
int main() {
// ucitavamo granice intervala
int a, b;
cin >> a >> b;
// odredjujemo broj i zbir po modulu 1000000 prostih brojeva iz
// intervala [a, b]
int broj, zbir;
prostiUIntevalu(a, b, broj, zbir);
// prijavljujemo rezultat
cout << broj << " " << zbir << endl;
return 0;
}Сложеност. Анализа сложености је компликованија и захтева одређено (додуше веома елементарно) познавање теорије бројева. Проценимо број извршавања тела унутрашње петље. У почетном кораку спољне петље прецртава се око \(\frac{n}{2}\) елемената. У наредном, око \(\frac{n}{3}\). У наредном кораку је број \(4\) већ прецртан, па се не прецртава ништа. У наредном се прецртава око \(\frac{n}{5}\), након тога опет ништа, затим \(\frac{n}{7}\) итд. У последњем кораку се прецртава око \(\frac{n}{\sqrt{n}}\) елемената. Дакле, број прецртавања је највише
\[\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \ldots + \frac{n}{\sqrt{n}} = n \cdot \left( \sum_{\substack{d\ \mathrm{prost},\\ d \leq \sqrt{n}}} \frac{1}{d} \right)\]
Број је заправо и мањи, јер приликом прецртавања у унутрашњој петљи прецртавање не крећемо од \(d\), већ од \(d^2\), али за потребе лакшег одређивања горње границе сложености користићемо претходну оцену.
Још је велики Ојлер открио да се збир \(H(m) = 1 + 1/2 + 1/3 + \ldots + 1/m = \sum_{d \leq m} \frac{1}{d}\) (такозвани хармонијски збир) асимптотски понаша слично функцији \(\log{m}\) (разлика између ове две функције тежи такозваној Ојлер-Маскеронијевој константи \(\gamma \approx 0.5772156649\)), па самим тим знамо да тај збир дивергира. Такође, открио је да када се сабирање врши само по простим бројевима, тада се збир понаша као логаритам хармонијског збира, тј. као \(\log{\log{m}}\) (па је и он дивергентан). Дакле, у нашем примеру можемо закључити да је број прецртавања једнак \(n \cdot \log{\log{\sqrt{n}}}\). Пошто је \(\log{\log{\sqrt{n}}} = \log{\log{n^{\frac{1}{2}}}} = \log{\left(\frac{1}{2}\log{n}\right)} = \log{\frac{1}{2}} + \log{\log{n}}\), под претпоставком да је сабирање бројева (које се користи у имплементацији петљи) константне сложености, важи да је сложеност Ератостеновог сита \(O(n \cdot \log{\log{n}})\). Иако није линеарна, функција \(\log{\log{n}}\) толико споро расте, да се за све практичне потребе Ератостеново сито може сматрати линеарним у односу на \(n\) (што је доста спорије само од испитивања да ли је број \(n\) прост, што има сложеност \(O(\sqrt{n})\), али је брже од проверавања сваког броја појединачно које је сложености \(O(n\sqrt{n})\)).