factorizacion

kati
25 de Noviembre del 2004
hola!
Necesito hacer un programa que factorice un número, por ejemplo, si el número es 12, la respuesta sería 1*2*2*3. Por favor, necesito su ayuda, no se como hacerlo, muchas gracias! :)

kati

xscorpio
25 de Noviembre del 2004
Primero q nada, un numero se puede factorizar de muchas maneras. Y para saberlas todas tienes que descomponerlo en su factorización Canónica (producto de potencias de primos)

Mira, primero saca todos los primos menores o iguales a N, por decir, éso es fácil
(para saber si un número es primo basta con tomar K y dividirlo entre todos los números menores o iguales a sqrt(K), si ninguno lo divide, entonces K es primo)
Una vez q tengas la cantidad y cuáles son los primos
simplemente empieza a contar cuantas veces entra ese factor en N.
Ya que tengas la factorización canónica sólo te queda combinar todos los posibles productos para sacar todas las factorizaciones, aunque quizá puedas intentar el vago BruteForce de alguna manera

chuidiang
25 de Noviembre del 2004
Hola:

No conozco ningún método infalible para cualquier número por grande que sea.
Necesitas en primer lugar una tabla de numeros primos. Hazla todo lo grande que consideres necesario. Sáltate el 1.

int [] primos = {2, 3, 5, 7, ...}

Luego es simplemente ir mirando si la operacion módulo % entre el numero dado y el número primo es 0

if ((numero % primos[i]) == 0)
{
// es divisible.
numero = numero / primos[i];
}

Se bueno.