Exercice 75
Ecrire un programme en python qui renvoie pour un entier n donné les tuples (p , q) dont le plus grand diviseurs commun pgcd(p,q) est premier.
Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
# coding: utf-8 # fonction qui calcul le pgcd de deux nombres def pgcd(a,b): # calcul du plus grand commun diviseur if b==0: return a else: # algorithme d'euclide recursif r=a%b return pgcd(b,r) # fonction qui teste la primalité d'un nombre def testPrim(n): # On initialise le nombre de diviseur de n à 0 numberOfDivisors = 0 for i in range(1,n+1): # tant que i est un diviseur de n on incrémente le nombre de diviseurs: numberOfDivisors if n%i == 0: numberOfDivisors = numberOfDivisors + 1 # le nombre n est premier si et seulement si numberOfDivisors == 2 if numberOfDivisors == 2: return True else: return False # liste des couples (p,q) vérifiant pgcd(p,q) est premier def tuple_pgcd_premier(n): # initialisation de la liste recherchée listTuple = [] for p in range(1, n+1): for q in range(1, n+1): if testPrim(pgcd(p , q)): listTuple.append((p,q)) return listTuple # Exemple n = 10 print(tuple_pgcd_premier(n)) # affiche: """ [(2, 2), (2, 4), (2, 6), (2, 8), (2, 10), (3, 3), (3, 6), (3, 9), (4, 2), (4, 6), (4, 10), (5, 5), (5, 10), (6, 2), (6, 3), (6, 4), (6, 8), (6, 9), (6, 10), (7, 7), (8, 2), (8, 6), (8, 10), (9, 3), (9, 6), (10, 2), (10, 4), (10, 5), (10, 6), (10, 8)] """ |
Younes Derfoufi
CRMEF OUJDA
1 thought on “Solution Exercice 75: algorithme python qui détermine la liste des couples dont le pgcd est premier”