...
Termenii $[(k*p)/p],[(k*p+1)/p]...[((k+1)*p-1)/p]$ au valoarea $k$
Termenii $[((k+1)*p)/p]...[N/p]$ au valoarea $k+1$

Astfel $k = [N/p]-1$ iar $S(N, p) = k*(k+1)/2*p + (k+1)*(N-(k+1)*p+1)$. Putem acum calcula $Nr(N, p)$ in $O(log{~p~} N)$. Factorizarea numarului $B$ se poate face in $O(√ B)$, iar numarul mediu al factorilor primi din descompunerea lui $B$ este $ln ln B$, complexitatea finala a rezolvarii fiind $O(√ B + ln ln B*log{~p~} N)$.

Astfel $k = [N/p]-1$ iar $S(N, p) = k*(k+1)/2*p + (k+1)*(N-(k+1)*p+1)$. Putem acum calcula $Nr(N, p)$ in $O(log{~p~} N)$. Factorizarea numarului $B$ se poate face in $O( &rad; B)$.

h2. 'Puteri':problema/puteri