Encontrar el número con el primer número de divisores?

Question

El problema es encontrar el número de números en [l,r] que el primer número de divisores. Ejemplo de $l=1,r=10$ La respuesta es $6$ desde $2,3,4,5,7,9$ son los números de tener el primer número de divisores

las restricciones se $l,r\le10^{12}$

y $r-l\le10^6$. Alguien me puede ayudar con la solución más rápida?

Aquí está mi enfoque

I stored primes  3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 in an array.
Loop through i=1 to 1000000
   if i is prime
       for j in primes
           calculate val=i^(j-1)
              add the val to answer list
for each query [l,r], the answer is all primes in [l,r]+ 
                     the numbers in the list in range [l,r]

pero encontrar todos los números primos en [l,r] toma demasiado tiempo. Cualquier sugesstion?

Answer 1

Mientras que la factorización prima no es exactamente lo que sucederá al instante para números grandes, se puede determinar el número de divisores de un número utilizando los exponentes de la descomposición en factores primos.

Para cada distinto poder en un número de la descomposición en factores primos, hay una integral exponente. Añadir 1 a cada uno de estos poderes, se multiplican los números resultantes, y usted tendrá que obtener el número de divisores que dividen incluso en el número original.

Algunos ejemplos para demostrar el poder de este hecho (de la que no puedo recordar una rigurosa prueba).

Ejemplo 1: 60. La descomposición en factores primos de 60 $2^23^15^1$. Sólo mirando a cada uno de los exponentes, hemos 2,1,1. Agregar uno a cada uno de ellos para obtener 3,2,2 y multiplicar para obtener 3*2*2 = 12. Esto significa que el 60 tiene 12 divisores (incluyendo 1 y 60). De hecho, los divisores positivos de 60 años son, en orden ascendente, 1,2,3,4,5,6,10,12,15,20,30,60.

Ejemplo 2: 17. 17 es un número primo, por lo que su descomposición en factores primos es (explícitamente con exponentes) 17^1. Tomar el exponente 1, agregar uno a ella para obtener 2, y ahora usted tiene el número de divisores positivos de 17: 1,17.

Ejemplo 3: $p$ donde $p$ es cualquier prime. No hace falta decir, la descomposición en factores primos es $p^1$, y los divisores positivos de $p$ 1,$p$. Dado que el número de divisores es siempre de 2 (que es primo), podemos concluir que todos los números primos tienen un primer número de divisores.

Ahora podemos considerar compuestos. Cada número natural $n\geq 1$ debe tener 1 y $n$ al menos en su primer divisor lista. Para cada divisor $d$$n$, con la correspondiente divisor $d/n$ que mantiene el número de divisores incluso. El único caso especial es cuando $d=\frac{n}{d} \implies d^2 = n$. Pero, a continuación, $d$ es simplemente la raíz cuadrada de $n$ (!) y sólo ocurren una vez en la lista de $n$'s divisores, lo que produce un número impar de divisores. Así que el único compuesto de números con un número impar de divisores son cuadrados perfectos. No hay necesidad de comprobar cualquier no-cuadrado número compuesto porque van a tener un número de al menos 4 divisores.

Computacional Pro-Tip: cuando se buscan todos los números en el intervalo de $[a,b]$, "simplemente" en la lista de los números primos en el intervalo. A continuación, asigne $m = \lfloor \sqrt{a} \rfloor$, e $n = \lceil \sqrt{b} \rceil$. Encontrar la factorización prima de cada número natural en el intervalo de $[m,n]$, el doble de cada uno de los exponentes en dicha factorización en primos, agregar uno a cada exponente, se multiplican todos ellos como antes, y determinar si este producto es primo. Si es así, sólo anexar el cuadrado de un entero correspondiente a la lista que sigue la pista de los números con un primer número de divisores positivos.

Answer 2

Su respuesta es simplemente el recuento de los números primos, más algunos extras números de $p^{2^k},k\geq 1,$ donde $p$ es primo, o, más en general, todos los números de la forma $p^{2^k},k\geq 0$ $p$ prime.

Ver esto para más detalles.

Por cierto, yo también estoy tratando este problema de codechef...pero no CA todavía :(