Python - Nivel 18 - Reto 10 - Descomponer un número en sus factores primos

ACLARACIÓN IMPORTANTE:
En este video llevamos a cabo una función que descompone un número en los factores primos de los que está compuesto. Pero debido a las limitaciones de los tipos de datos flotantes en python, y por tanto a la precisión de la división, este programa puede dar errores en números muy elevados.

La forma de python para expresar números muy elevados es mediante el uso de la e:

15_000_000_000_000_000 == 1.5e+16
True

Por tanto, cuando se hace una división de un número muy elevado el resultado puede dar problemas de precisión, lo que para el programa que nos ocupa se puede solucionar usando en su lugar la división entera, ya que no usa la notación con e:

141674867017458786543455 / 2
7.083743350872939e+22

141674867017458786543455 // 2
70837433508729393271727

Por tanto, el programa optimizado incluiría poner // en vez de / y añadir el condicional:

if n == 1:
return primos

para evitar que el programa siga iterando cuando ya no hay más primos:

============================

def descomponer(n):
primos = []
for i in range(2, n+1):
while n % i == 0:
n = n // i
#print(primos,i, n)
if n == 1:
return primos

============================

print(descomponer(63525567747779927405))

Si no se utilizase la división entera, este número tan elevado daría error debido como decíamos
a la notación con e para números muy elevados que utiliza python.

---------------------------------------------------------------------

RETO PARA RESOLVER:

Hacer una función que halla los múltiplos de un número (algunos pues son infinitos).
Hacer una función que halla los divisores de un número (todos).

---------------------------------------------------------------------

[isidromanuel]

De forma recursiva ;)


def prime_factors(n):
if n == 1: return []
for div in range(2, n + 1):
if n % div == 0: return [div] + prime_factors(n // div)

[ivanlegranbizarro]

No entiendo porque estos vídeos no tienen más visitas ni más likes. Muy buena explicación, muchísimas gracias.

[konanfly]

gran canal muchísimas gracias por tu aporte amigo c:

[medicenanonimo]

Yo hice esta funcion que es muy ineficiente para los peores casos, ah y si el factor se repite no lo retorna xd
import math
def factores_primos(n): #17
factores=[]
quiebre=True
i=2
while i<=n and quiebre==True: #2, ..., 17
for j in range(2, i): #vamos a dividir con los mismos factores
if i%j==0: #2/2=1 | 0
break
else: #for termina normal entnces es primo i y podemos usarlo:
if n/i==1.0:
factores.append(i)
quiebre=False
elif n%i==0:
factores.append(i)
i+=1
return factores
print(factores_primos(60)) #output: [2, 3, 5]

[horkoser]

He creado la siguiente función que utiliza como parámetros la lista de primos correspondiente al número y el número del que queremos obtener su factores:
def descomponer(lista_primos, numero):
lista_factores = []
contador = 0
while contador < len(lista_primos):
if numero % lista_primos[contador] == 0:

numero = numero / lista_primos[contador]
else:
contador += 1
return lista_factores

[anez]

Yo lo hice así:

def descomposicion_primos(n):

factores_primos = []

while True:

for i in range(2, int(n)+1):
if n % i == 0:
n = n / i
factores_primos.append(i)
break
else:
break

return factores_primos

[francescoeriani]

3:50 En vez de poner n = n / i podias haber utilizado n/=i

[JaimeLopez-psfk]

Que sucede si el numero a descomponer es el sys.maxsize ? Puede haber overflow ?

[anthonythemortal]

Para mí no funciona.
Me sale typeerror: not all arguments converted during string formatting

[paularuiz]

Hola, a mi no me funciona el programa, y no se porqué puede ser. Lo único que añadí al suyo fue que le dije que pidiera al usuario que introduciera n. He introducido n y lleva 5 minutos cargando, no me sale nada. He probado más tarde a quitarle lo que yo misma le había añadido y sigue sin funcionar, ¿alguna idea?

[jorgeandrespedrozazapata]

En el while n % i = 0: me sale error de syntax, uso Visual studio code, ayuda :(

[geraldinenataliahenriquezs]

lo ejecuto en Python y no funciona, que puede ser?