Factorizar Número en Python

(Descarga directa del script aquí)

El script que voy a explicar ahora se encarga de expresar un número como un producto de números primos.

El script que voy a explicar ahora se encarga de expresar un número como un producto de números primos. Funciona para cualquier número - por grande que sea - aunque cuanto mayor es la longitud del número, más suele tardar.

A grandes ragos, el script funciona asi:

1) El programa tiene una lista interna de números primos

2) Intenta dividir el número que le indicamos (por ejemplo el 265) por cada uno de los números de esta lista , empezando por el más pequeño. (lo intenta con el 2, si no es divisible con el 3, etc)

3) Una vez encuentra el número primo más pequeño por el que es divisible el número (en este caso, el 5 es el número primo más pequeño por el que 265 es divisible) divide el primer número (265) entre el número primo (5), y obtiene un nuevo número (el 53 en este caso)

4)Vuelve al paso 2, pero utilizando el número obtenido en el paso anterior(el 53).

-> El programa finaliza este bucle cuando el número que obtenemos en el paso 3 es primo.(El 53 es primo, por lo tanto se detiene una vez lo obtiene, y nos muestra que 265 es igual a 5 * 53)

-> La lista inicial de números primos tiene hasta el 17, pero es muy probable que haga falta utilizar más números (En el caso anterior, hace falta ampliar la lista de números primos hasta el 53). Para ampliar esta lista, el programa usa la función "aniadir_primo".

Bueno, y aquí va el script:

# Writed in Python 2.4.2 (#67, Sep 28 2005, 12:41:11) [MSC v.1310 32 bit (Intel)] on win32.

# Factorizar un numero

numero = int(raw_input('Introduzca numero para factorizar : --> '))

def factorizar(numero): # Funcion principal

#print 'numero:',numero

num_ini = numero

num = num_ini

num_fact = ''

primos = [1,2,3,5,7,11,13,17]

# Con primos = [1,2] tambien funcionaria

seguir = True

while seguir:

if num ==1: # Se acabo la descomposicion

break

#print 'iteracion', primos[-1]

for primo in primos[1:]:

if num%primo == 0: # Si es divisible

num = num/primo

num_fact += str(primo)+'*'

break # Saltamos el for

# Si estamos aqui es que no es divisible entre los numeros de la lista que teniamos:

#hay que ampliar la lista.

primos = aniadir_primo(primos, num)

# Aqui volvemos a ejecutar todo el programa a ver si con la nueva lista conseguimos algo.

num_fact = num_fact[:-1]

print

print 'descomposicion factorial: ',num_fact

raw_input()

def aniadir_primo(primos, fin): # Funcion para añadir nuevos numeros primos

#print 'fin',fin

l_p = primos

# Establecer c

c = int(primos[-1])+1

while 1:

if es_primo(c, l_p):

l_p.append(c)

return l_p

if c == fin:

# Aqui no se que poner

return 'hola'

c += 1

def es_primo(num, primos): # Funcion que dado un número comprueba si es primo

l_p = primos[1:] # Para quitar el 1

for primo in l_p:

divisor = primo

cociente = float(num)/float(primo)

if cociente < divisor: return True # Si pasa esto es que ya no tiene

#sentido seguir dividiendo pues no me dara enteros, y por eso paro: es primo

if num%primo == 0: return False

return True

factorizar(numero)

Tal =)