Kernel: Python 3

TP fait avec Mohamed Ait Ali

Récursivité : décomposition en facteurs premiers

Objectif : Ces exercices ont pour but de vous faire écrire des fonctions récursives manipulant des paramètres de type nombre. On demande donc que toutes les fonction écrites soient récursives (usage des boucles interdit). Il est également important de bien tester vos fonctions.

On cherche dans ce TP à calculer une liste représentant la décomposition en facteurs premiers d’un entier donné, c'est-à-dire son écriture sous la forme d'un produit de facteurs $p^e$ tels que $p$ est un nombre premier et $e$ est un entier le plus grand possible.

Par exemple, $2^2 \times 3^1 \times 5^2$ est la décomposition en facteurs premiers de $300$ .

Dans un second temps, on cherchera à optimiser les fonctions écrites.

Échauffement : recomposition et affichage

On représentera en Python la décomposition en facteurs premiers d'un nombre entier $n \geq 2$ comme une liste de couples de la forme (p, e) indiquant que le facteur $p^e$ apparaît dans la décomposition de $n$ . On supposera que cette liste est triée par facteurs croissants, et ne contient aucun exposant nul.

Par exemple, la décomposition de $13$ est [(13,1)] car $13$ est un nombre premier et $13 = 13^1$ , et celle de $300$ est [(2, 2), (3, 1), (5, 2)] car $300 = 2^2 \times 3^1 \times 5^2$ .

Complétez la fonction récursive recomposition qui étant donnée une liste sous cette forme calcule la valeur du nombre correspondant.

In [15]:

#TP Fait avec Mohamed Ait Ali
def recomposition(liste_facteurs):
    """Renvoie le nombre dont la décomposition en facteurs premiers 
    est fournie.
    """
    if len(liste_facteurs) == 1:
        return(liste_facteurs[0][0]**liste_facteurs[0][1])
    else:
        liste_2=liste_facteurs*1
        liste_2.pop(0)
        return(liste_facteurs[0][0]**liste_facteurs[0][1])*(recomposition(liste_2))

print(recomposition([(2, 2), (3, 1), (5, 2)]) == 300)

Out[15]:

True

Complétez la fonction récursive chaine_decomp(liste_facteurs) qui renvoie une chaîne représentant sous une forme lisible la décomposition en facteurs premiers fournie en paramètre.

Par exemple, chaine_decomp([(2, 2), (3, 1), (5, 2)]) pourrait renvoyer la chaîne "2**2 * 3 * 5**2".

In [3]:

def chaine_decomp(liste_facteurs):
    """Renvoie une chaîne de caractères représentant la décomposition 
    en facteurs premiers fournie.
    """
    if len(liste_facteurs)==1:
        return(str(liste_facteurs[0][0]) + str("**") + str(liste_facteurs[0][1]))

    else:
        liste_2=liste_facteurs*1
        liste_2.pop(0)
        return(str(liste_facteurs[0][0]) + str("**") + str(liste_facteurs[0][1])+ str(" * ") +chaine_decomp(liste_2))

print(chaine_decomp([(2, 2), (3, 1), (5, 2)]))
print(chaine_decomp([(2, 2), (3, 1), (5, 2)]) == "2**2 * 3 * 5**2")

Out[3]:

2**2 * 3**1 * 5**2
False

Test de primalité

Complétez la fonction suivante, puis testez-la.

In [4]:

from math import sqrt
def est_premier(n, div=2):
    """Renvoie True si n n'a aucun diviseur supérieur ou égal à div (et 
    différent de lui-même).
    
    Exception : renvoie False si n est inférieur ou égal à 1.
    Si div n'est pas précisé lors de l'appel, renvoie True si n est premier.
    """
    if n <= 1:
        return False  # Ni 1, ni 0 ne sont premiers
    elif div >= (sqrt(n))+1:
        return True
    elif n%div == 0:  # Si div est un diviseur de n
        return False
    else:
        # Si aucun de ces cas n'est vérifié
        return(est_premier(n,div+1)) # Faire ici un appel récursif !
        
# Écrivez vos tests ici :
#A modifier plus tard
est_premier(5)

Out[4]:

True

Essayez de déterminer si le nombre 64231 est premier.

In [5]:

# Écrivez votre test ici.
est_premier(64231)

Out[5]:

True

Amélioration

Le nombre d'appels récursifs effectués par un appel à est_premier(n) est de l'ordre de n. Ceci peut poser des problèmes, comme on l'a vu dans le test précédent. Comment améliorer la fonction pour diminuer le nombre d'appels récursifs nécessaires ? Faites la modification nécessaire ci-dessus. Testez à nouveau la primalité de $64231$ .

D'un premier à l'autre

À l’aide de la fonction est_premier programmée à la section précédente, complétez la fonction ci-dessous qui calcule le plus petit nombre premier strictement supérieur à $p$ .

Par exemple, premier_suivant(15) renvoie 17, premier_suivant(11) renvoie 13.

In [6]:

def premier_suivant(p):
    """Renvoie le plus petit nombre premier strictement supérieur à p."""
    if est_premier(p+1):
        return p+1
    else:
        return(premier_suivant(p+1))
    
print(premier_suivant(11) == 13)
print(premier_suivant(12) == 13)

Out[6]:

True
True

Exposant d'un facteur premier

Complétez la fonction ci-dessous qui étant donnés $n$ et $p$ renvoie l’exposant de $p$ dans la décomposition en facteurs premiers de $n$ , ainsi que le nombre restant à décomposer.

Par exemple, comme $600$ est divisible trois fois par 2 et que $600 = 2^3 \times 75$ , exposant(600,2) devra renvoyer (3,75), et comme 600 n’est pas divisible par 7, exposant(600,7) devra renvoyer (0,600).

In [7]:

def exposant(n, p, puis = 0):
    """Renvoie l'exposant de p dans la décomposition en facteurs premiers de
    n, et le nombre restant à décomposer."""
    if n%p != 0 :
        return(puis,n)
    else:
        return(exposant(n//p,p, puis+1))

print(exposant(600,2))
print(exposant(600,2) == (3, 75))
#A faire

Out[7]:

(3, 75)
True

Décomposition

À l’aide de la fonction précédente, complétez la fonction récursive decomposition(n) suivante, qui doit renvoyer la liste des couples représentant la décomposition en facteurs premiers de n.

Par exemple, decomposition(13) renverra [(13,1)], et decomposition(300) renverra [(2, 2), (3, 1), (5, 2)].

In [14]:

def decomposition(n, p=2, l=[]):
    """Renvoie une chaîne décrivant la décomposition en facteurs premiers de
    n. Si l'argument p est donné, la recherche de facteur commence à
    cette valeur."""
    if est_premier(n):
        l.append((n,1))
        return(l)
    else:
        (x,y)=exposant(n,p)
        if x == 0:
            return(l)
        l.append((p,x))
        return(decomposition(n,premier_suivant(p),l))
        


print(decomposition(13) == [(13,1)])
print(decomposition(300, p=2, l=[]))
print(decomposition(300, p=2, l=[]) == [(2, 2), (3, 1), (5, 2)])
#A faire

Out[14]:

True
[(2, 2), (3, 1), (5, 2)]
True

Calcul du PGCD et du PPCM

Vous connaissez l'algorithme d'Euclide qui calcule le plus grand commun diviseur à deux entiers $a$ et $b$ . Cependant, si l'on connaît la décomposition en facteurs premiers de $a$ et $b$ , il est facile d'en déduire leur PGCD : en effet, la décomposition en facteurs premiers du PGCD de $a$ et $b$ contient tous les facteurs premiers communs à $a$ et $b$ , et l'exposant de chacun de ces facteurs est le minimum des exposants de ce facteur dans la décomposition de $a$ et de $b$ .

Par exemple le PGCD de $75$ et $90$ est $15 = 3^1 \times 5^1$ car $75 = 3^1 \times 5^2$ et $90 = 2^1 \times 3^2 \times 5^1$ .

Complétez la fonction suivante qui calcule la décomposition en facteurs premiers du PGCD de deux nombres à partir de leurs décompositions.

In [1]:

def pgcd_decomp(decomp_a, decomp_b, l=[], i=0,j=0):
    if i >= len(decomp_a):
        return(l)
    elif j >= len(decomp_b):
        return(pgcd_decomp(decomp_a,decomp_b,l,i+1,j=0))
    else:
        if decomp_a[i][0] != decomp_b[j][0]:
            return(pgcd_decomp(decomp_a,decomp_b,l,i,j+1))
        else:
            if decomp_a[i][1]< decomp_b[j][1]:
                l.append(decomp_a[i])
            else:
                l.append(decomp_b[j])
            return(pgcd_decomp(decomp_a,decomp_b,l,i+1,j=0))
    return(l)

print(pgcd_decomp([(3, 1), (5, 2)], [(2, 1), (3, 2), (5, 1)]))            
print(pgcd_decomp([(3, 1), (5, 2)], [(2, 1), (3, 2), (5, 1)]) == [(3, 1), (5, 1)])

Out[1]:

[(3, 1), (5, 1)]
False

Compléter la fonction ppcm_decomp suivante calculant la décomposition du PPCM de deux nombres en fonction de leurs décompositions.

In [64]:

def ppcm_decomp(decomp_a, decomp_b, l=[], i=0, j=0, a=0):
    if a == 2:
        return(l)
    elif i>= len(decomp_a):
        i=0
        j=0
        return(ppcm_decomp(decomp_b, decomp_a,l,i,j,a+1))
    elif j>= len(decomp_b):
        if decomp_a[i] not in l:
            l.append(decomp_a[i])
        j=0
        return(ppcm_decomp(decomp_a, decomp_b,l ,i+1, j,a))
    else:
        if decomp_a[i][0] != decomp_b[j][0]:
            return(ppcm_decomp(decomp_a, decomp_b, l, i, j+1,a))
        else:
            if decomp_a[i][1]> decomp_b[j][1]:
                if decomp_a[i] not in l:
                    l.append(decomp_a[i])
            else:
                if decomp_b[j] not in l:
                    l.append(decomp_b[j])
                j=0
            return(ppcm_decomp(decomp_a, decomp_b, l, i+1, j,a))

print(ppcm_decomp([(3, 1), (5, 2)], [(2, 1), (3, 2), (5, 1)]))        
print(ppcm_decomp([(3, 1), (5, 2)], [(2, 1), (3, 2), (5, 1)]) == [(2, 1), (3, 2), (5, 2)])

Out[64]:

[(3, 2), (5, 2), (2, 1)]
False

Optimisation des fonctions

Les différentes fonctions réalisés lors des questions précédentes ont tendance à effectuer plusieurs fois les mêmes calculs, par exemple :

pour le test de primalité, il n'est pas nécessaire de tester le diviseur 4 si on sait que le nombre n'est pas divisible par 2 ;
pour la décomposition, si on décompose plusieurs entiers successivement, on peut être amené à tester plusieurs fois si le même entier est premier ou non, et on risque également de décomposer plusieurs fois le même nombre.

Dans la suite, nous allons utiliser une liste et un dictionnaire pour mémoriser les nombres premiers que nous rencontrons, ainsi que les décompositions déjà calculées, ceci afin d'être sûrs de ne jamais les recalculer une seconde fois.

Test de primalité optimisé

Ré-écrivons les fonctions est_premier et premier_suivant de sorte que l'on ne fasse que des divisions par des nombres premiers. Pour ce faire on stockera dans une liste tous les nombres premiers inférieurs à une certaine valeur.

In [71]:

def est_premier_opti(n, L, indice_premier=0):
    """ Vérifie si n est premier en ne divisant que par les nombres 
    premiers de L. S'il manque des nombres, on appelera 'premier_suivant_opti'
    pour compléter la liste. 
    Le nombre `indice_premier` représente l'indice dans L du nombre premier 
    que l'on est en train de traiter. 
    """
    if n<= 1:
        return False
    if L[len(L)-1] > n:
        return True
    # Il faut ajouter à L les nombres premier qu'il nous manque
    if indice_premier >= len(L):
        L.append(premier_suivant_opti(L[-1], L))
        return est_premier_opti(n, L,indice_premier)


def premier_suivant_opti(n, L, indice_premier=0):
    """ Renvoie le plus petit nombre premier strictement supérieur à n
    à partir de L[indice_premier] en utilisant la fonction 'est_premier_opti.
    """
    if est_premier_opti(L[indice_premier],L, indice_premier):
        if n < L[indice_premier]:       
            return(L[indice_premier])
    else:
        return(premier_suivant_opti(n,L,indice_premier+1))

In [72]:

P = [2]  # liste des nombres premiers connus initialement

print(est_premier_opti(11, P))
print(est_premier_opti(64231, P))
print(not est_premier_opti(64233, P))

print(premier_suivant_opti(15, P)==17)
print(permier_suivant_opti(11, P)==13)
print(premier_suivant_opti(0, P)==2)

print(P)  # liste des nombres premiers connus en fin de calcul

Out[72]:

None
None
True

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-72-dd65b07232e4> in <module>()
      5 print(not est_premier_opti(64233, P))
      6 
----> 7 print(premier_suivant_opti(15, P)==17)
      8 print(permier_suivant_opti(11, P)==13)
      9 print(premier_suivant_opti(0, P)==2)
<ipython-input-71-7f913ed451f9> in premier_suivant_opti(n, L, indice_premier)
     24             return(L[indice_premier])
     25     else:
---> 26         return(premier_suivant_opti(n,L,indice_premier+1))

<ipython-input-71-7f913ed451f9> in premier_suivant_opti(n, L, indice_premier)
     20     à partir de L[indice_premier] en utilisant la fonction 'est_premier_opti.
     21     """
---> 22     if est_premier_opti(L[indice_premier],L, indice_premier):
     23         if n < L[indice_premier]:
     24             return(L[indice_premier])
IndexError: list index out of range

Calcul de décomposition optimisé

Proposer une fonction decomposition_opti qui ne calcule pas plusieurs fois la primalité d'un même entier et qui ne calculerait qu'une fois chaque décomposition si l'utilisateur décompose plusieurs nombres.

In [ ]:

def decomposition_opti(n, L, mem):  # déterminer le type du paramètre `mem`
    """Renvoie une liste décrivant la décomposition en facteurs premiers de
    `n`. La fonction doit stocker dans `L` les nombres premiers déjà vus, 
    et dans `mem` les décompositions déjà traitées. 
    """
    ...

In [ ]:

mem = ...  # état initial de la structure de données auxiliaire

for n in range(100):
    print(chaine_decomp(decomposition_opti(n, L, mem)))
    
print(mem)  # état après calculs

Comparaison avec les versions précédentes

(Bonus) Pour se convaincre de l'efficacité de nos optimisations, nous allons comparer le nombre d'opérations (par exemple de divisions et calculs de reste) effectuées au total par le dernier test effectué ci-dessus. Modifiez l'ensemble des fonctions précédentes afin d'effectuer ce comptage, et comparez les résultats obtenus.

In [ ]:

In [ ]: