Te sugerimos que pruebes esta solución en un ambiente controlado antes de pasarlo a producción, un saludo.
Solución:
Dmitriy tiene razón en que querrás que el Tamiz de Atkin genere la lista principal, pero no creo que eso solucione todo el problema. Ahora que tiene una lista de números primos, deberá ver cuántos de esos números primos actúan como divisores (y con qué frecuencia).
Aquí hay algo de python para el algoritmo. Mire aquí y busque “Asunto: matemática – necesita algoritmo de divisores”. Sin embargo, simplemente cuente la cantidad de elementos en la lista en lugar de devolverlos.
Aquí hay un Dr. Math que explica qué es exactamente lo que necesitas hacer matemáticamente.
Esencialmente se reduce a si su número n es:n = a^x * b^y * c^z
(donde a, b y c son los divisores primos de n y x, y y z son el número de veces que se repite ese divisor), entonces el recuento total de todos los divisores es:(x + 1) * (y + 1) * (z + 1).
Editar: Por cierto, para encontrar a, b, c, etc. querrás hacer lo que equivale a un algoritmo codicioso si lo entiendo correctamente. Comience con su divisor primo más grande y multiplíquelo por sí mismo hasta que una multiplicación adicional exceda el número n. Luego muévase al siguiente factor más bajo y multiplique el número primo anterior ^ número de veces que se multiplicó por el número primo actual y siga multiplicando por el número primo hasta que el siguiente exceda n… etc. Lleve un registro del número de veces que multiplica el número primo divisores juntos y aplicar esos números en la fórmula anterior.
No estoy 100% seguro de la descripción de mi algoritmo, pero si no es así, es algo similar.
Hay un lote más técnicas para factorizar que el tamiz de Atkin. Por ejemplo, supongamos que queremos factorizar 5893. Bueno, su raíz cuadrada es 76,76… Ahora intentaremos escribir 5893 como un producto de cuadrados. Bien (77*77 – 5893) = 36 que es 6 al cuadrado, entonces 5893 = 77*77 – 6*6 = (77 + 6)(77-6) = 83*71. Si eso no hubiera funcionado, habríamos visto si 78*78 – 5893 era un cuadrado perfecto. Y así. Con esta técnica, puede probar rápidamente factores cercanos a la raíz cuadrada de n mucho más rápido que probando números primos individuales. Si combina esta técnica para descartar números primos grandes con una criba, tendrá un método de factorización mucho mejor que con la criba sola.
Y esta es solo una de la gran cantidad de técnicas que se han desarrollado. Este es bastante simple. Le llevaría mucho tiempo aprender, digamos, suficiente teoría de números para comprender las técnicas de factorización basadas en curvas elípticas. (Sé que existen. No los entiendo.)
Por lo tanto, a menos que esté tratando con números enteros pequeños, no intentaría resolver ese problema por mí mismo. En cambio, trataría de encontrar una manera de usar algo como la biblioteca PARI que ya tiene implementada una solución altamente eficiente. Con eso puedo factorizar un número aleatorio de 40 dígitos como 124321342332143213122323434312213424231341 en aproximadamente 0,05 segundos. (Su factorización, en caso de que te lo preguntes, es 29*439*1321*157907*284749*33843676813*4857795469949. Estoy bastante seguro de que no lo resolvió usando el tamiz de Atkin…)
@Yasky
Su función de divisores tiene un error en el sentido de que no funciona correctamente para cuadrados perfectos.
Probar:
int divisors(int x)
int limit = x;
int numberOfDivisors = 0;
if (x == 1) return 1;
for (int i = 1; i < limit; ++i)
if (x % i == 0)
limit = x / i;
if (limit != i)
numberOfDivisors++;
numberOfDivisors++;
return numberOfDivisors;
Aquí puedes ver las comentarios y valoraciones de los lectores
Si conservas alguna indecisión o forma de aclarar nuestro sección puedes realizar una crónica y con deseo lo leeremos.