Factorización en Números Primos - dambort/algos GitHub Wiki

Problema:

Dado un numero entero hallar sus factores primos.

Ejemplos:

  1. Si x = 515; Salida: sus factores primos son: 5 103

  2. Si x = 20; Salida: sus factores primos son: 2 2 5

  3. Si x = 10350; Salida: sus factores primos son: 2 3 3 5 5 23

  4. Si x = 7; Salida: sus factores primos son: 7

Idea del algoritmo:

Dentro de un bucle, se verifica si el numero ingresado es divisible por el primo mas chico (2), si es así le realiza la división, y cuando el numero ingresado ya no sea divisible por 2 el valor del primo mas chico se incrementa hasta el siguiente primo y se repite el proceso mientras el numero ingresado sea mayor a 1.

El algoritmo genera un vector stl, al cual se le va agregando de forma dinámica los valores de los factores primos, el algoritmo puede modificarse para retornar un vector estático o que solo los muestre los valores por pantalla.

Código

Disponible en Enciclopedia Algoritmos C++, factorizar en primos.

Ejemplo de uso

Disponible en ejemplo calcular número e,

Complejidad: -

En Ideone

Problemas en sitios jueces que se pueden resolver con factorización en primos.

Colaborador del artículo: