Exercice 10
Créer un algorithme en Python sous forme de fonction qui prend en argument un nombre entier positif n et renvoie True si le nombre n est produit de deux nombres premiers et False si non.
Exemple : si n = 10 , la fonction renvoie True. Si n = 8 la fonction renvoie False.
Solution
Pour résoudre cet exercice, on procède en deux étapes. La première consiste à créer une fonction qui teste la primalité d’un nombre entier positif, c’est-à-dire vérifier s’il est premier ou non. Cette fonction nous permettra ensuite d’identifier facilement les nombres premiers parmi les diviseurs possibles. La deuxième étape consiste à exploiter cette fonction pour déterminer si l’entier donné peut s’exprimer comme le produit de deux nombres premiers. Pour cela, on parcourt les nombres entiers à partir de 2, et dès qu’un nombre premier divise l’entier étudié, on vérifie si le quotient obtenu est également premier. Si c’est le cas, alors l’entier est bien le produit de deux nombres premiers ; sinon, on conclut qu’il ne possède pas cette propriété.
|
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 |
# -------------------------------------------------- # Fonction qui teste si un entier x est un nombre premier # -------------------------------------------------- def est_premier(x): # Tout entier inférieur à 2 n'est pas premier if x < 2: return False # On teste s il existe un diviseur entre 2 et √x for i in range(2, int(x**0.5) + 1): if x % i == 0: # si i divise x, alors x n est pas premier return False return True # aucun diviseur → x est premier # -------------------------------------------------- # Fonction qui teste si n est le produit de deux nombres premiers # -------------------------------------------------- def est_produit_de_premiers(n): # On teste tous les nombres p possibles de 2 à n-1 for p in range(2, n): # Si p est premier et p divise n : if est_premier(p) and n % p == 0: q = n // p # on calcule q = n / p # Si q est aussi premier, alors n = p × q if est_premier(q): return True # Aucun couple (p, q) trouvé → n n est pas le produit de deux premiers return False # Tester l algorithme print(est_produit_de_premiers(10)) # True (10 = 2 × 5) print(est_produit_de_premiers(8)) # False (8 ne = pas p × q avec p et q premiers) print(est_produit_de_premiers(21)) # True (21 = 3 × 7) |
Younes Derfoufi
CRMEF OUJDA
