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.