Exercice 11
Un nombre de Chen est un nombre premier, nommée ainsi relativement au nom du mathématicien chinois Chen Jingrun. Un nombre premier p est appelé un nombre premier de Chen si p+2 est soit un autre nombre premier, soit le produit de deux nombres premiers distincts (c'est-à-dire un nombre semi-premier).
1) - Ecrire un programme en langage Python sous forme de fonction test_chen(n) qui prends en argument un entier n et renvoie True si l'entier n est premier de chen et False si non. (On pourra utiliser l'exercice précédent Exercice 10)
2) - Ecrire un programme en Python sous forme de fonction nommée list_chen(n) qui prends en argument un entier n et renvoie la liste des nombres premiers de Chen p<=n.
Exemple: si n = 45, l'algorithme renvoie la liste [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] (43 est un nombre premier qui n'est pas de Chen)
Solution
Pour résoudre cet exercice, nous devons d’abord rappeler qu’un nombre premier de Chen est un nombre premier n tel que n+2 soit soit un nombre premier, soit un produit de deux nombres premiers (appelé semi-premier). Pour traduire cette définition en programme Python, nous créons d’abord la fonction est_premier(n) qui vérifie si un nombre est premier. Ensuite, nous utilisons la fonction est_produit_de_premiers(n) qui permet de tester si un entier peut être écrit comme produit de deux nombres premiers. Enfin, la fonction principale test_chen(n) commence par vérifier si n est premier ; si ce n’est pas le cas, elle renvoie False. Si n est premier, elle calcule n+2 et renvoie True si n+2 est premier ou s’il est un produit de deux nombres premiers. Cette démarche permet de déterminer si un nombre vérifie la définition mathématique d’un nombre premier de Chen.
Questionv1:
|
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 |
# Fonction qui teste si un nombre entier n est premier def est_premier(n): if n < 2: return False # On teste tous les diviseurs possibles de 2 jusqu'à racine(n) for i in range(2, int(n**0.5) + 1): if n % i == 0: # Si on trouve un diviseur alors n n'est pas premier return False return True # Aucun diviseur trouvé, donc n est premier # Fonction qui teste si un entier n est le produit de deux nombres premiers def est_produit_de_premiers(n): # On parcourt tous les possibles facteurs premiers for i in range(2, n): if est_premier(i) and n % i == 0: # Si i est premier et divise n j = n // i # L'autre facteur if est_premier(j): # On vérifie si j est aussi premier return True # n = i * j est bien un produit de deux nombres premiers return False # Fonction qui teste si n est un nombre premier de Chen def test_chen(n): # Condition obligatoire : n doit être premier if not est_premier(n): return False m = n + 2 # On calcule n + 2 # Premier cas : n+2 est premier if est_premier(m): return True # Deuxième cas : n+2 est un produit de deux premiers if est_produit_de_premiers(m): return True # Sinon n n'est pas un premier de Chen return False # Exemples d’utilisation print(test_chen(5)) # True (car 5+2=7 est premier) print(test_chen(7)) # True (car 7+2=9 = 3*3 est produit de deux premiers) print(test_chen(11)) # True (car 11+2=13 est premier) print(test_chen(8)) # False (8 n'est pas premier) |
Question 2:
|
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 |
# Fonction qui teste si n est premier de Chen def test_chen(n): # Condition de base : n doit être premier if not est_premier(n): return False m = n + 2 # On regarde n + 2 # Premier cas : n+2 est premier if est_premier(m): return True # Deuxième cas : n+2 est un produit de deux premiers (semi-premier) if est_produit_de_premiers(m): return True # Sinon, n n'est pas un premier de Chen return False # Renvoie la liste des nombres premiers de Chen p <= n def list_chen(n): chen = [] # liste vide au départ # On parcourt tous les entiers de 2 à n for p in range(2, n + 1): if test_chen(p): # Si p est un premier de Chen chen.append(p) # On l'ajoute à la liste return chen #Exemple d’utilisation print(list_chen(45)) # Output : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] |
Younes Derfoufi
CRMEF OUJDA
