Descomponer en factores primos

En esta lección obtendrás los factores primos de un número.

Se prueba dividir por 2 mientras se pueda, luego por 3, y así sucesivamente. Cada división exacta añade ese divisor a la lista.

El código de ejemplo descompone un número y muestra los factores.

Lo que resulta poco intuitivo es que no hace falta comprobar si el divisor es primo. Cuando llegas al 4, todos los factores 2 ya se han extraído, así que ninguna potencia de 2 puede dividir lo que queda. Los divisores compuestos nunca encajan.

Fíjate en que el parámetro n se modifica dentro de la función. En C los parámetros son copias, así que eso no afecta a quien llamó — es seguro, y a la vez es una práctica que conviene señalar, porque quien lea la función más abajo ya no sabe cuál era el valor original.

El bucle interior es el que hace el trabajo real: un número como 8 tiene el factor 2 tres veces, y hay que dividir mientras se pueda antes de pasar al siguiente candidato.

Conviene tener presente el límite: este método es rápido con números pequeños y completamente inviable con números de cientos de cifras. Esa dificultad es lo que sostiene la seguridad de RSA.