‘Dados dos enteros N y D, tendrás que encontrar cuántos de los factores de N son divisibles por D.’ Aquí N es un número muy grande y D no es necesariamente un número primo. ¿Cuál es la solución matemática para este problema?

El número de factores de N que son divisibles por D (cuando D divide a N de manera uniforme) es igual al número de factores de N / D. Hay un método estándar para calcular el número de divisores que un número ha dado su factorización prima: sume uno al exponente de cada factor primo y multiplique todos estos números juntos.

Como ejemplo, encontremos el número de factores de 60 que son divisibles por 5. Esto es igual al número de factores de 60/5 = 12. La factorización prima de 12 es [matemática] 2 ^ 2 \ veces 3 ^ 1 [/ matemática]. Agregar uno a cada exponente da 3 y 2, que podemos multiplicar para obtener 6.

Los 6 divisores de 60 que son divisibles por 5 son 5, 10, 15, 20, 30 y 60.

¿Cómo podemos decir que esto funciona? En lugar de una prueba, simplemente divida todos los factores anteriores entre 5 y vea que son 1, 2, 3, 4, 6 y 12. Estos son precisamente los divisores de 12. Debe quedar claro que los dos problemas son equivalentes .

Una manera fácil es usar el máximo común divisor de N y D, generalmente denotado por g: = gcd (N, D).

Si a es un factor de N tal que una D divisoria, entonces a debe dividir este número entero g. Hay un método rápido llamado algoritmo de Euclides para encontrar tal gcd g. Por otro lado, si a divide a g, entonces a es un factor de N y también divide a D.

Por lo tanto, su pregunta se reduce para encontrar cuántos divisores de tal gcd g, lo que requiere que factorice g por completo.

El mejor método en este punto, creo, es el tamiz de campo de número general. Encontrar un algoritmo de tiempo polinómico, aunque dudo si existiría, para la factorización es uno de los problemas más interesantes en la investigación actual.

Si N no es divisible por D, entonces ninguno de los factores de N lo es. Entonces tu respuesta es cero. Si N se describe como un número decimal y D tiene factores distintos de 2 y 5, entonces deberá procesar todos los dígitos de N para determinar si N es divisible por D. Si D es de la forma (2 ^ a) * (5 ^ b), entonces solo tiene que mirar el máximo (a, b), pero de lo contrario, tendrá que lidiar con todos los dígitos de N.

Si N es divisible por D, entonces su respuesta es igual al número de factores únicos de N / D. Si N es demasiado grande para hacer esto, entonces no hay forma de evitarlo.