Descomposición primaria de un número entero: métodos para determinar los factores primos $ p_1, p_2, ..., p_r$ y poderes $k_1,k_2, ..., k_r$

Question

Cualquier número entero n puede escribirse de la forma

$ n = p_1^{k_1}p_2^{k_2} ... p_r^{k_r} $ ,

donde los poderes $ k_1, k_2, ...,k_r $ son números enteros y $ p_1, p_2, ..., p_r$ son primos.

Ahora me interesa saber si hay métodos más rápidos para encontrar las potencias, que no sean de prueba y error. Por ejemplo, si quisiera escribir un número grande como 567 788 en la forma anterior, y se viera algo así:

$567 788 = p_1^{k_1}p_2^{k_2}p_3^{k_3} $

qué métodos podrían aplicarse para determinar los factores primos pertinentes $ p$ y por qué poder $k$ para elevar cada primo $p$ ?

Answer 1

Para encontrar las potencias, hay que iterar, pero hay formas eficientes de hacerlo.

Para empezar, cada vez que encuentres un factor primo $p$ , factor de $n$ antes de buscar nuevos factores. Para su ejemplo:

$$567788=2*283894=2*2*141947$$

Factorizamos $2$ hasta que no salga más, entonces busca el siguiente factor. 3,5,7,11 no son factores, 13 sí, así que

$$=2*2*13*10919$$

13 no se divide de nuevo, sigue probando factores hasta encontrar 61 que funcione

$$=2*2*13*61*179$$

Sabemos que 179 es primo sin tener que probar ningún otro factor primo porque ya sabemos que no puede ser divisible por nada menos que el último factor primo que encontramos (61) que es más que $\sqrt{179}$ . Fíjate que no hemos tenido que intentar dividir por ningún número mayor que 61, que es bastante menos que $\sqrt{567788}\approx750$ .

Sin duda, hay otras formas de hacerlo, pero ésta es sencilla de entender y de aplicar, y le ahorra muchos cálculos con respecto a su método anterior.