Factorització d’un enter en nombres primers

1. Dissenya la funció factoritza(n) que descomposa un nombre enter donat, n, en els seus factors primers i retorna una llista amb tots els factors trobats.

   Per fer la descomposició, cal esbrinar pel nombre 2 i per tots els senars que van des del 3 fins a la meitat de n quins són divisors de n. Quan trobem un divisor de n, dividirem n per aquest divisor tantes vegades com sigui possible. Quan n val 1, cal aturar el procés.

   Per exemple, els factors primers de l’enter n=100 poden ser el 2 i els senars entre 3 i 50 (100/2). Trobem que 2 divideix 100 dues vegades: 100/2= 50, 50/2=25. Aleshores n passa a valer 25.

   Amb el 25 provem a partir del 3:

   • El 3 no divideix 25

   • El 5 és divisor de 25 dues vegades: 25/5= 5, 5/5=1

   • Ara n val 1 i ja no hem de comprovar més possibles divisors.

La funció ha de passar les proves següents:

>>> factoritza (100)
[2, 2, 5, 5]
>>> factoritza (500940)
[2, 2, 3, 3, 5, 11, 11, 23]
>>> factoritza (496)
[2, 2, 2, 2, 31]
 

Nota

Pots descarregar el fitxer amb tests factoritza.txt

Solució

Disposeu de solucions al fitxer factoritza.py