Calcul du PGCD avec Python
Ecrire une fonction Python nommée diviseurs qui prend en argument un nombre entier naturel non nul n et qui retourne la liste de ses diviseurs triés par ordre croissant.
Tester votre fonction à l'aide des instructions suivantes :
>>> diviseurs(1) >>> diviseurs(2) >>> diviseurs(100) >>> diviseurs(101)
Rappel :
L'opérateur % renvoie le reste de la division euclidienne de deux entiers.En utilisant la fonction diviseurs de la question précédente, écrire une fonction est_premier qui prend un argument entier et retourne un booléen valant True si l'argument est un nombre premier et False dans le cas contraire.
Tester votre fonction à l'aide des instructions suivantes :
>>> est_premier(1) >>> est_premier(2) >>> est_premier(100) >>> est_premier(101)
L'opérateur Python in permet de savoir si un élément appartient ou non à une liste.
On l'utilise de la manière suivante :liste = ['rouge', 'vert', 'jaune'] print('rouge' in liste) # affiche True print('bleu' in liste) # affiche False
À l'aide de la fonction diviseurs de la première question et de l'opérateur in écrire une fonction nommée inter qui prend deux listes en arguments et qui renvoie une troisième liste contenant les éléments communs aux deux listes.Par exemple on souhaite que l'instruction inter(['a', 'b', 'c'], ['b', 'c', 'd', 'e']) retourne la liste ['b', 'c'].
Tester votre fonction à l'aide des instructions suivantes :
>>> inter(['a', 'b', 'c'], ['b', 'c', 'd', 'e']) >>> inter([1,2,4], [1, 2, 3, 6]) >>> inter([1,2,3], [4,5,6])
À l'aide des fonctions définies aux questions 1 et 3, écrire une fonction nommée pgcd qui prend deux entiers naturels en arguments et qui retourne leur PGCD.
Tester votre fonction à l'aide des instructions suivantes :
>>> pgcd(10, 11) >>> pgcd(15,20) >>> pgcd(501,666) >>> pgcd(110,121)
Corrigé
On peut coder la fonction à l'aide d'une boucle for.
L'instruction range(1, n+1) retourne les entiers naturels compris, au sens large, entre 1 et n. On teste ensuite si l'entier i divise n grâce à l'instruction if n
def diviseurs(n) : liste = [] for i in range(1, n+1) : if n % i == 0 : liste.append(i) return liste
Le mode de construction de cette liste fait que celle-ci est automatiquement triée par ordre croissant.Il est également possible et plus concis d'utiliser une définition de la liste en compréhension :
def diviseurs(n) : return [i for i in range(1,n+1) if n % i == 0]
Les tests proposés dans l'énoncé donnent les résultats suivants :
>>> diviseurs(12) [1, 2, 3, 4, 6, 12] >>> diviseurs(1) [1] >>> diviseurs(2) [1, 2] >>> diviseurs(100) [1, 2, 4, 5, 10, 20, 25, 50, 100] >>> diviseurs(101) [1, 101]
Un nombre entier naturel est premier si et seulement s'il possède exactement deux diviseurs : 1 et lui-même.
Il suffit donc de tester la longueur de la liste retournée par la fonction diviseurs() pour déterminer si l'argument est premier. La commande len(diviseurs(n)) == 2 renvoie True si cette liste contient deux nombres et False sinon :
def est_premier(n) : return len(diviseurs(n)) == 2
Cette fonction donne les résultats suivants :
>>> est_premier(1) False >>> est_premier(2) True >>> est_premier(100) False >>> est_premier(101) True
Voici un exemple de fonction qui donne le résultat souhaité (mais qui n'est pas le plus concis :
def inter(liste1, liste2) : liste3=[] for i in range(len(liste1)) : a = liste1[i] if a in liste2 : liste3.append(a) return liste3
Pour chaque élément de la première liste, on regarde s'il appartient à la seconde liste grâce à l'opérateur in ; si c'est le cas, on ajoute cet élément à la réponse.Voici le résultat des tests :
>>> inter(['a', 'b', 'c'], ['b', 'c', 'd', 'e']) ['b', 'c'] >>> inter([1,2,4], [1, 2, 3, 6]) [1, 2] >>> inter([1,2,3], [4,5,6]) []
La liste des diviseurs étant ordonnées par ordre croissant, il suffit de retourner le dernier élément de la liste des diviseurs communs (obtenue en faisant l'intersection des deux listes de diviseurs) :
Attention : les éléments d'une liste sont indexés de 0 à len(liste)-1. L'indice du dernier élément est donc len(liste)-1.
def pgcd(a, b) : diviseurs_communs = inter(diviseurs(a), diviseurs(b)) return diviseurs_communs[len(diviseurs_communs)-1]
Les tests demandés donnent les résultats ci-dessous :
>>> pgcd(10, 11) 1 >>> pgcd(15,20) 5 >>> pgcd(501,666) 3 >>> pgcd(110,121) 11