La fonction ifactors (que l’on peut trouver dans Xcas par exemple) peut être implémentée en Python.
Elle permet d’obtenir la liste des diviseurs d’un nombre ainsi que leur exposant dans la décomposition ne produit de facteurs premiers.
J’ai déjà traité le sujet de la décomposition en produits de facteurs premiers dans cet article (parlant de pythontex) et dans celui-ci (parlant de \(\LaTeX\)). Mais j’avais envie de me pencher sur la question algorithmique…
ifactors en Python: une première approche
J’ai commencé par créer une fonction prime, retournant la liste des nombres premiers jusqu’à n (nombre à décomposer), puis une seconde nommée ifactors retournant un dictionnaire rempli des facteurs accompagnés de leur exposant.
def prime(n): P = [2] for i in range( 2 , n ): prime_number = True for j in P: if i % j == 0: prime_number = False if prime_number == True: P.append(i) return P def ifactors(n): D = {} for k in prime(n): if n != 1: exposant = 0 while (n % k == 0): exposant += 1 n /= k if exposant != 0: D[k] = exposant return D
>>> ifactors(1025)
{5: 2, 41: 1}
Cela me donne bien la décomposition \( 1025 = 5^2 \times 41 \), mais ça se gatte pour:
>>> ifactors(3963960)
C’était en effet une idée stupide que de vouloir construire la liste des nombres premiers inférieurs à n pour l’objectif fixé.
En effet, la fonction prime(3963960) est bien trop lente !
ifactors en Python: une variante de la première approche
Pour améliorer cette première approche, il serait bon de ne pas faire appel à la liste des nombres premiers, puisque c’est elle qui fout la merde dans le bouzin… On va donc être un peu bourrins et changer la ligne 17:
def ifactors(n): D = {} for k in range(2,n+1): if n != 1: exposant = 0 while (n % k == 0): exposant += 1 n /= k if exposant != 0: D[k] = exposant return D
>>> ifactors(3963960)
{2: 3, 3: 2, 5: 1, 7: 1, 11: 2, 13: 1}
Le résultat apparaît presque instantanément. C’est beaucoup mieux, même si c’est bien bourrin de parcourir tous les nombres entiers de 2 à n…
ifactors en Python: une troisième approche
Voici une autre approche:
def ifactors(n): D = {} P = [ 2 ] while n!= 1: # on construit la liste des nombres premiers jusqu'à Racine_carrée(n) for i in range( P[-1]+1 , int(n**0.5) ): # on commence à P[-1] histoire de pas recommencer du début prime_number = True for j in P: if i % j == 0: prime_number = False if prime_number == True: P.append(i) # On cherche s'il y a un diviseur à n for k in P: exposant = 0 while (n % k == 0): exposant += 1 n /= k if exposant != 0: D[k] = exposant return D
Elle fonction plutôt bien pour l’exemple précédent, mais quand on augmente le nombre, là, ce n’est plus la même chose…
Une solution pour les grands nombres
Les plus expérimenté·e·s auront vu que dans la logique des scripts précédents, il y avait un problème à l’origine du problème de lenteur. Avec la méthode précédente, on y est presque…
Pour éviter les problèmes de lenteur, il faudrait éviter de stocker des valeurs dans une liste qui ne sert à rien.
def ifactors(n): D = {} i = 2 while n > 1: exposant = 0 while n%i == 0: exposant += 1 n = n/i if exposant != 0: D[i] = exposant i = i + 1 return D
Cette fonction suffit largement… et en plus, elle est bien plus courte que les précédentes!
>>> ifactors(764104821480)
{2: 3, 3: 2, 5: 1, 7: 1, 11: 2, 13: 1, 17: 2, 23: 1, 29: 1}
Temps d’exécution négligeable… car il n’y a que des divisions!
Cette solution avait d’ailleurs été proposée dans mon article sur pythontex cité au début.
Amélioration de l’affichage
Comme je suis du genre plutôt perfectionniste, j’ai maintenant envie d’améliorer l’affichage.
def ifactors(n , decomp = False): D = {} i = 2 while n > 1: exposant = 0 while n%i == 0: exposant += 1 n = n/i if exposant != 0: D[i] = exposant i = i + 1 if decomp == False: return D else: L_exp = [ 0x2070, 0x00B9, 0x00B2, 0x00B3, 0x2074, 0x2075, 0x2076, 0x2077, 0x2078, 0x2079 ] r = '' for prime,exposant in D.items(): exposant = str(exposant) for i in exposant: exposant = exposant.replace(i,chr(L_exp[int(i)])) if r != '': r += ' × ' r += str(prime) + exposant return r
J’ai ajouté une option à la fonction qui permet d’obtenir un affichage de la décomposition en produits de facteurs premier plus lisible:
>>> ifactors(764104821480 , True)
2³ × 3² × 5¹ × 7¹ × 11² × 13¹ × 17² × 23¹ × 29¹
Remarque: la commande ifactor (sans le « s » à la fin) de Xcas permet d’obtenir cette écriture.
Bonjour, modifier la valeur de n dans la boucle :
for k in range(2, n+1):
c’est toujours acrobatique. Mais merci pour la lecture de cet article qui m’a bien aidé.
Bonjour. Il n’y a aucune erreur dans les boucle.J’ai vérifié lors de la rédaction de l’article, et encore aujourd’hui (on ne sait jamais bien sûr), mais tout me semble bon. Merci.
Acrobatique mais très malin dans la version 3 de ifactors. J’aime beaucoup.