Densitate

Problema cere sa raspundeti la intrebari de forma: "Cate numere prime sunt intre a si b?" (a si b inclusiv), cu 0 < a ≤ b ≤ N < 500000. Complexitatea dorita pentru preprocesare este O(N log logN) si cea pentru query este de O(1).
In primul rand trebuie sa stim care sunt numele prime intre 1 si N. Algoritmul clasic de verificare a divizibilitatii unui numar x cu toate valorile pana la x/2 este ineficient, avand complexitate O(x), acesta poate fi optimizat pana la O(sqrt(x)) daca se verifica numai numerele intre 2 si sqrt(x), dar acesta este eficient doar daca se testeaza primalitatea unui singur numar. Noi insa dorim sa stim toate numrele prime intre 1 si N si pentru asta se foloseste Ciurul lui Eratostene . Acest algoritm tine un sir V in care V[i]=1 are semnificatia ca i este prim si V[i] = 0 inseamna ca i nu e prim. La pasul i, daca i este prim, se seteaza V[k] = 0 pentru toti multiplii k lui i pana la N. Complexitatea acestui algoritm este O(N/2 + N/3 + N/5 ... ) = O(N log logN)
La pasul al doilea trebuie sa raspundem la intrebari. Sa parcurgem toate valorile intre a si b ar fi ineficient. Tinem insa un sir de sume cumulate S unde S[i] reprezinta numarul de numere prime mai mici sau egale decat i, astfel S[i] = S[i-1] + V[i]. Raspunsul se calculeaza ca S[b] - S[a-1]. Metoda sumelor cumulate poate fi extinsa pentru un spatiu N^k.