Usando búsqueda binaria para buscar el ~k~-ésimo número que cumple la condición el problema se convierte en contar cuantos números son libres de cubos menores o iguales a un ~n~.

Sean los conjuntos ~A(p_1), A(p_2), \ldots A(p_h)~ donde ~A(p_i)~ es el conjunto de los números entre ~1~ y ~n~ que cumplen que son múltiplos del cubo del ~p~-ésimo primo entonces se cumple que ~A(p_i) = n / p_i ^ 3~ y la unión de estos conjuntos es el complemento de la cantidad de números libres de cubos, es decir ~T = U - P~ donde ~U = n~ y ~P~ sería la cardinalidad de la unión de los conjuntos. Para calcular esto se puede usar el Principio de Inclusiones y Exclusiones.

Si se usa directamente el principio (usando por ejemplo una máscara de bits) no va a entrar en tiempo, pero se puede notar que si ~x~ es un cubo perfecto libre de cuadrados entonces ~x = p_1 ^ 3 \cdot p_2 ^ 3 \cdot \ldots \cdot p_k ^ 3~ y ~A(p_1, p_2, \ldots, p_k) = A(x)~ por lo que lo único que haría falta es hallar todos los números que son libres de cuadrados y elevarlos al cubo (hay ~O(\sqrt[3] n)~ de estos números) y en dependencia de la paridad de primos en su factorización se suma o se resta en la inclusión exclusión.

Complejidad: ~O(\sqrt[3] n \cdot \log n)~