El número de divisores de un cuadrado es el divisor de la función convoluciona con el cuadrado de la función de Möbius (ver $g(n)$ aquí)
$$e(n)=d(n^2)=(d\star\mu^2)(n)$$
y ya
$$\mu^2(n)=\sum_{d^2|n}\mu(d)$$
por lo tanto
$$e(n)=\sum_{un \left| n \right.} d \left( \frac{n}{a} \right) \sum_{b^2 \left| a
\right.} \mu \left( b \right)$$
que puede ser simplificado y reescribe como
$$e(n)=\sum_{b^2 \left| n \right.} \mu \left( b \right) d_3 \left( \frac{n}{b^2}
\right)$$
donde $d_3(n)$ es el número de maneras en que un número dado se puede escribir como un producto de tres enteros. Esta identidad puede ser verificado por señalar que $e(n)$ es multiplicativo y la comprobación en el primer poderes que los rendimientos de $e(p^a)={2a+1}$ y puede ser comparado con $d(p^a)={a+1}$. En particular, tenga en cuenta que $d_3(p^a)={\binom{a+2}{2}}$ (ver $d_k$ aquí).
Entonces la suma de la cantidad de divisores de los números al cuadrado se puede calcular como:
$$E(x)=\sum_{n\le x} d(n^2)
=\sum_{n \leq x} \sum_{b^2 \left| n \right.} \mu \left( b \right) d_3 \left( \frac{n}{b^2}
\right)$$
que puede ser reorganizado como:
$$E(x)=\sum_{b \leq \sqrt{x}} \mu \left( b \right) \sum_{n \leq x / b^2} d_3
\left( n \right)$$
$$E(x)=\sum_{a \leq \sqrt{x}} \mu \left( a \right) D_3 \left( \frac{x}{a^2} \right)$$
donde $D_3$ es el summatory función de $d_3$. Desde $D_3(x)$ puede ser calculado en $O(x^{2/3})$ tiempo la complejidad de uso de las tres dimensiones analógica de la hipérbola método, $E(x)$ también puede por lo tanto ser calculado en
$$O(\int_{a=1}^\sqrt{x}{(\frac{x}{a^2})}^{2/3}da)=O(x^{2/3})$$
que es mejor que el de $O(x)$ como se desee.
Por tomar un $O(x^{1/3})$ algoritmo para calcular $D(x)$ y la utilizan para $D_3(x)$, esta obligado puede ser reducido a $O(x^{5/9})$. Usted puede encontrar un algoritmo y una fórmula para $D_3(x)$ en mi artículo aquí que utiliza la notación $T(n)$$T_3(n)$.
