Problema se poate rezolva mai bine intr-o complexitate $O(N*lg^2^ N)$ folosind structuri de date avansate, astfel transformandu-se intr-o problema de clasele 11-12 grea, sau chiar o problema de finala. Lasam aceasta rezolvare ca exercitiu pentru cititor.

 
h2. Sum
 
h3. (problema usoara, clasa a 10a)
 
Vom face o prima observatie:
 
* $(n, d) = 1 <=> (n, n - d) = 1, (n, n + d) = 1$
 
Fie {$a = phi (n)$}, indicatorul lui Euler. Fie $b$ numarul de numere prime cu $n$ cuprinse intre $n$ si {$2 * n$}.
Deoarece {$(n, d) = 1 <=> (n, n + d) = 1, a &le; b$}. Deoarece {$(n, d) = 1 <=> (n, n - d) = 1, b &le; a => b = a$}. Fie {$x{~1~}, x{~2~}, .. x{~a~}$} numerele $< n$ si prime cu $n$ => numerele cuprinse intre $n$ si $2 * n$ si prime cu $n$ vor fi {$x{~1~} + n, x{~2~} + n, .. x{~a~} + n$}.
 
Conform observatiei facute, $(n, n - x{~1~}) = 1, (n, n - x{~2~}) = 1, .. (n, n - x{~a~}) = 1$ =>
 
$x{~a~} = n - x{~1~} <=> x{~1~} + x{~a~} = n$
$x{~a-1~} = n - x{~2~} <=> x{~2~} + x{~a-1~} = n$
...
$x{~1~} = n - x{~a~} <=> x{~a~} + x{~1~} = n$
 
Fie $S1$ suma numerelor prime cu $n$ si mai mici ca {$n$}, fie $S2$ suma numerelor prime cu {$n$}, cuprinse intre $n$ si {$2 * n$}.
Adunand cele a egalitati, obtinem $2 * S1 = a * n$ => {$S1 = (a * n) / 2$}.
 
$S2 = a * n + S1$ => {$S1 + S2 = 2 * a * n$}.
 
Se foloseste o singura data ciurul lui Erathostene pentru a determina functia phi pentru toate intrebarile. Se poate consulta "articolul":http://infoarena.ro/Ciurul-lui-Erathostene despre cirulul lui Erathostene.
 

h2. Pavare 2
h3. (problema grea, clasa a 10a)