El enfoque ingenuo
Cuente el número de divisores para cada N en el rango dado.
Esto llevará un tiempo y no es necesario
La visión:
- ¿Cuál es la factorización prima de 2500?
- ¿Cómo puede BDS resolver el problema de Israel y Palestina?
- ¿Cómo podemos resolver la sexta pregunta en esto?
- ¿Existe un algoritmo para calcular todas las posibles poliominós libres para un número n?
- El promedio de los números [matemática] m [/ matemática] es [matemática] n ^ 4. [/ matemática] El promedio de los números [matemática] n [/ matemática] es [matemática] m ^ 4 [/ matemática]. ¿Cuál será el promedio de los números [matemática] (m + n) [/ matemática]?
Suponga que [matemáticas] N = \ prod_ {i = 1} ^ k p_i ^ {e_i} [/ matemáticas]
Donde [math] p_i [/ math] es primo y [math] {e_i} [/ math] es el exponente correspondiente.
Por el teorema fundamental de la aritmética, esta factorización prima es única.
Si m divide N, entonces [matemática] m = \ prod_ {i = 1} ^ k p_i ^ {a_i} [/ matemática] con [matemática] a_i \ leq e_i [/ matemática] para cada i.
Entonces, para cada i, [math] a_i \ in (0,1,2,…, e_i) [/ math]. Eso es [matemática] e_i + 1 [/ matemática] posibilidades.
Así, el número de divisores de N es:
[matemáticas] R = \ prod_ {i = 1} ^ k e_i + 1 [/ matemáticas]
De acuerdo … ¿Cómo me ayuda eso? ¿Esperas que encuentre la factorización prima de todos estos números?
¡No! ¡En cambio, vamos a CONSTRUIR el número más pequeño posible con la mayoría de los divisores!
Tenga en cuenta que el número de divisores no depende de los primos, sino solo de sus exponentes correspondientes. Entonces el número más pequeño con divisores R satisfará las siguientes tres propiedades:
- [matemáticas] R = \ prod_ {i = 1} ^ k e_i + 1 [/ matemáticas]
- [matemáticas] e_i \ geq e_ {i + 1} [/ matemáticas] para todo i
- [math] p_i [/ math] es el número primo [math] i ^ {th} [/ math]
De hecho, eso es suficiente para ser el número más pequeño con esos divisores R.
Construyendo nuestro algoritmo
Comience con una matriz de ceros correspondientes a los valores [math] {e_i} [/ math].
Puede iterar con bastante rapidez sobre los valores posibles en esta matriz para encontrar el mayor número de divisores que puede tener un número menor que 10 ^ 18.
Puede enlazar la entrada [math] i ^ {th} [/ math] con [math] \ frac {\ log (N)} {\ log (p_i)} [/ math]. Solo tenga cuidado de verificar que no haya excedido N.
Usaremos logaritmos para comparar valores para ahorrar tiempo, por lo que todo lo que necesitamos es [matemáticas] \ sum_ {i = 1} ^ k {e_i} \ log (p_i) \ leq \ log (N) [/ matemáticas]
¡Pero este algoritmo se puede mejorar aún más!
Aplicar un algoritmo codicioso (¿puedes averiguar cómo?) Y hacer un trabajo de casos cuidadoso después (esta es la parte difícil: no hacer el trabajo de casos, pero estar seguro de que estás hecho) puede acelerar las cosas aún más.
Dicho esto, la iteración anterior es suficiente para sus propósitos.