Un número es libre de cuadrados si y solo si ningún cuadrado de un primo lo divide, por lo que podemos restringir nuestra atención a solo verificar cuadrados de primos (no cuadrados de números arbitrarios).
Creo que la mejor manera de lograr esto es con un tamiz.
Primero genere una lista de primos [math] p_i [/ math] hasta [math] \ sqrt [2] {10 ^ {(N + 1)}} [/ math]. Necesitamos poder detectar algo de [matemática] p ^ 2 [/ matemática] que es solo ligeramente menor que [matemática] 10 ^ {N + 1} [/ matemática].
Luego, inicialice una matriz booleana de tamaño [matemática] 10 ^ {N + 1} -10 ^ N [/ matemática], con una entrada para cada número de N dígitos. Marcaremos aquellos números que no son libres de cuadrados, dejando solo los números libres de cuadrados. (Una optimización simple es omitir todos los múltiplos de 4, pero eso reduce el tamaño de la matriz en solo un 25%.) Específicamente, para cada primo [math] p_i [/ math], repita sobre [math] k [/ math] de modo que [matemática] 10 ^ N \ leq kp_i ^ 2 <10 ^ {N + 1} [/ matemática] y marque [matemática] kp_i ^ 2 [/ matemática] como "no cuadrada". Después de que se haya marcado cada múltiplo de un cuadrado de un primo, los números restantes sin marcar son libres de cuadrados y se pueden generar.
- Cómo resolver esta pregunta en Codeforces
- ¿Cómo funcionará la generalización (muy publicitada) de ‘Blockchain más allá de Bitcoin’?
- ¿Qué es un ejemplo de interpolación?
- Programación dinámica (DP): ¿Cuál es el número total de formas en que N dados pueden sumar S?
- Cómo demostrar que el algoritmo codicioso para el problema de la mochila 0-1 siempre obtiene al menos la mitad de los mejores resultados posibles
Si la matriz fuera demasiado grande, podemos ejecutar el tamiz en segmentos. Por ejemplo, primero tamiz en el rango [matemática] [10 ^ N, 2 * 10 ^ N) [/ matemática] luego [matemática] [2 * 10 ^ N, 3 * 10 ^ N) [/ matemática], etc. Convenientemente, no hay necesidad de transferir ninguna salida de un rango al siguiente. Si incluso la lista de primos es demasiado grande, existen técnicas para manejar eso también, pero de todos modos es probable que el tamaño de salida sea inviablemente grande.
La complejidad temporal de este procedimiento es incluso mejor que el tamiz de Eratóstenes. Cada número primo en nuestro rango elimina aproximadamente [matemática] 10 ^ {N + 1} / p ^ 2 [/ matemática] números no cuadrados, así que si dejamos [matemática] M = 10 ^ {N + 1} [/ matemática ] por conveniencia la complejidad es sobre
[matemáticas] M \ sum_ {p \ leq \ sqrt {M}} \ frac {1} {p ^ 2} [/ matemáticas]
La última suma converge a aproximadamente [matemáticas] 0.45 [/ matemáticas] a medida que M va al infinito, por lo que podemos tratarla como una constante. (Ver la suma del recíproco de los primos al cuadrado.) Por lo tanto, nuestro tiempo es esencialmente lineal en el tamaño del rango de números, o exponencial en [matemáticas] N [/ matemáticas].