Nombres premiers particuliers – Bac pratique – Section informatique – 2016
Sujet (Algo et programmation - Bac 2016)
Dans un contexte arithmétique, on définit les nombres premiers factoriels et les nombres premiers primoriels comme indiqué ci-après.
Un nombre PF est dit premier factoriel s'il vérifie les deux propriétés suivantes :
- PF est un nombre premier
- et PF s'écrit sous la forme d'un factoriel incrémenté ou décrémenté de 1 (PF F! + 1 ou PF = F! - 1), sachant que le factoriel de F noté F! est égal à F*(F-1)* *1
Exemples :
- 7 est un nombre premier factoriel car 7 est premier et il s'écrit sous la forme 3! + 1.
- 719 est un nombre premier factoriel car 719 est premier et il s'écrit sous la forme 6! -
Un nombre PP est dit premier primoriel s'il vérifie les deux propriétés suivantes :
- PP est un nombre premier
- et PP s'écrit sous la forme d'une primorielle incrémentée ou décrémentée de 1 (PP = P# + 1 ou PP = P# - 1), sachant que la primorielle de P notée P# est égale au produit des nombres premiers inférieurs ou égaux à P.
Exemples :
- 211 est un nombre premier primoriel car 211 est premier et il s'écrit sous la forme 7# + 1 En effet, 7# + 1 211=3*5*7 + 1 = 210 + 1 = 211
- 30029 est un nombre premier primoriel car 30029 est premier et il s'écrit sous la forme 13# - En effet, 13# - 1 = 2*3*5*7*11*13 - 1 = 30030 - 1 = 30029
Travail à faire :
Ecrire un programme en Python intitulé "Fac_Prim" qui permet d'afficher les N premiers nombres premiers factoriels et les N premiers nombres premiers primoriels (avec 2 < N < 5).
Solution Algorithmique
Dans cet algorithme, On va utiliser cinq fonctions et deux procédures:
- la fonction saisie()
- la fonction test_premier()
- la fonction factoriel()
- la fonction test_premier_factoriel()
- la fonction test_premier_primoriel()
- la procédure rechercher_nombres_premier_factoriel()
- la procédure rechercher_nombres_premier_primoriels
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 |
Algorithme Fac_Prim Debut # Saisie du nombre n (1 < n < 6) n <- saisie(1, 6) # Affichage des n premiers nombres premiers factoriels rechercher_nombres_premier_factoriel(n) # Affichage des n premiers nombres premiers primoriels rechercher_nombres_premier_primoriels(n) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction saisie
Le rôle de cette fonction est de permettre à l’utilisateur de saisir un entier n compris strictement entre deux bornes inf et sup.
1- La fonction saisie(inf, sup) demande à l’utilisateur d’entrer un entier n.
2- Elle vérifie que n appartient à l’intervalle ouvert ] inf , sup [ (c’est-à-dire inf < n < sup). 3- Tant que la valeur saisie n’est pas valide (n ≤ inf ou n ≥ sup), la fonction redemande la saisie. 4- Une fois une valeur correcte entrée, la fonction retourne n.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Fonction saisie(inf:entier, sup:entier):entier # Première saisie de n Ecrire('donner n tel que ', inf , '< n < ' , sup, ': ')) Lire(n) # Tant que n n’appartient pas à l’intervalle ]inf , sup[ # on redemande la saisie Tant que (n <= inf) ou (n >= sup) faire Ecrire('donner n tel que ', inf , '< n < ' , sup, ': ')) Lire(n) Fin tant que # Retourne la valeur valide retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction test_premier
Le fonction test_premier vérifie si un entier n est un nombre premier en testant sa divisibilité par les entiers compris entre 2 et la moitié de n.
1- On initialise i à 2, car 1 n’est pas considéré comme un diviseur dans le test de primalité.-
2- Cas particulier : Si n = 2, la fonction retourne directement True car 2 est un nombre premier.
3- Sinon :
Le programme teste si n est divisible par un entier i compris entre 2 et n//2.
Tant que i est strictement inférieur à n//2 et que i ne divise pas n, on incrémente i.
À la fin de la boucle :
4- Si n % i != 0, cela signifie qu’aucun diviseur n’a été trouvé → n est premier. Sinon, n n’est pas premier.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Fonction test_premier(n:entier):booleen i <- 2 # Cas particulier : 2 est premier Si n != 2 alors # Tester la divisibilité de n par les entiers de 2 à n//2 Tant que (i < n div 2) et (n mod i != 0) faire i <- i + 1 Fin tant que # Retourne Vrai si aucun diviseur n'est trouvé retourner (n mod i != 0) Si non retourner Vrai Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La fonction factoriel
Cette fonction permet de calculer et retourner le factoriel d’un entier positif n, noté n!.
1- La variable f est initialisée à 1.
2- Une boucle for multiplie successivement f par tous les entiers de 1 jusqu’à n. À la fin de la boucle, f contient la valeur de n! = 1 × 2 × 3 × … × n.
3- La fonction retourne cette valeur.
|
1 2 3 4 5 6 7 8 9 |
Fonction factoriel(n:entier):entier f <- 1 # Calcul de n! = 1 × 2 × ... × n Pour i de 1 à n faire f <- f * i Fin pour # Retourner la valeur du factoriel retourner f Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | entier |
| i | entier |
La fonction test_premier_factoriel
Cette fonction teste si un entier n est un nombre premier factoriel, c’est-à-dire un nombre premier qui peut s’écrire sous la forme F! + 1 ou F! − 1.
1- Test de primalité
La fonction commence par vérifier si n est un nombre premier à l’aide de la fonction test_premier.
Si n n’est pas premier, la fonction retourne immédiatement False.
2- Calcul des factoriels
Si n est premier, la fonction calcule successivement les factoriels F! pour F = 2, 3, 4, ....
À chaque étape, elle vérifie si n est égal à : F! + 1 ou F! − 1
3- Arrêt de la recherche
La boucle s’arrête lorsque le factoriel dépasse n ou lorsque l’une des deux égalités est vérifiée.
Résultat
4- La fonction retourne Vrai si n peut s’écrire sous la forme F! ± 1. Sinon, elle retourne Faux.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Fonction test_premier_factoriel(n:entier):booleen # Vérifier d'abord si n est premier Si test_premier(n) alors i <- 2 f <- 1 # Calculer les factoriels successifs jusqu'à dépasser n # et vérifier si n = F! + 1 ou n = F! - 1 Tant que (n != f - 1) et (n != f + 1) et ((f + 1) <= n) faire f <- factoriel(i) i <- i + 1 Fin tant que # Retourner True si n est égal à F! ± 1 retourner (n = f - 1) ou (n = f + 1) Sinon retourner Faux Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | entier |
| i | entier |
La fonction test_premier_primoriel
Cette fonction teste si un entier n est un nombre premier primoriel, c’est-à-dire un nombre premier qui peut s’écrire sous la forme P# + 1 ou P# − 1.
1- Vérification de la primalité
La fonction commence par vérifier si n est un nombre premier à l’aide de la fonction test_premier.
Si n n’est pas premier, la fonction retourne immédiatement False.
2- Calcul de la primorielle
Si n est premier, la fonction calcule progressivement la primorielle P#, qui correspond au produit des nombres premiers successifs (2, 3, 5, 7, …).
À chaque étape, la multiplication n’est effectuée que si i est un nombre premier.
3- Test de la condition primorielle
La fonction vérifie si n est égal à : P# + 1 ou P# − 1
La boucle s’arrête lorsque la valeur de la primorielle dépasse n ou lorsque l’égalité est vérifiée.
4- Résultat
La fonction retourne Vrai si n peut s’écrire sous la forme P# ± 1. Sinon, elle retourne Faux.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Fonction test_premier_primoriel(n:entier):booleen # Vérifier d'abord si n est premier Si test_premier(n) alors i <- 2 p <- 1 # Calculer les produits des nombres premiers successifs (primorielle) # et vérifier si n = P# + 1 ou n = P# - 1 Tant que (n != p - 1) et (n != p + 1) et ((p + 1) <= n) faire # Multiplier uniquement par les nombres premiers Si test_premier(i) alors p <- p * i Fin si i = i + 1 Fin pour # Retourner True si n est égal à P# ± 1 retourner (n = p - 1) ou (n = p + 1) Sinon retourner Faux Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| p | entier |
| i | entier |
La procédure rechercher_nombres_premier_factoriel
Cette procédure permet de rechercher et d’afficher les n premiers nombres premiers factoriels.
- La procédure affiche d’abord un message indiquant le nombre de valeurs recherchées.
- La variable cp sert de compteur pour le nombre de nombres premiers factoriels trouvés.
- La variable i, initialisée à 3, représente le nombre testé.
- Tant que le compteur cp est inférieur à n :
La procédure teste si i est un nombre premier factoriel à l’aide de la fonction test_premier_factoriel.
Si le test est vrai, i est affiché et le compteur est incrémenté.
La valeur de i est ensuite augmentée pour tester le nombre suivant.
- La recherche s’arrête dès que n nombres premiers factoriels ont été trouvés.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Procedure rechercher_nombres_premier_factoriel(n:entier) Ecrire('Les', n, 'nombres premiers factoriels sont :') cp <- 0 # Compteur de nombres trouvés i <- 3 # Début de la recherche à partir de 3 # Continuer la recherche jusqu'à trouver n nombres Tant que cp < n faire Si test_premier_factoriel(i) alors Ecrire(i,' ') cp <- cp + 1 Fin si i <- i + 1 Fin tant que Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| cp | entier |
| i | entier |
La procédure rechercher_nombres_premier_primoriels
Cette procédure permet de rechercher et d’afficher les n premiers nombres premiers primoriels.
- La procédure affiche d’abord un message indiquant le nombre de valeurs recherchées.
- La variable cp est utilisée comme compteur du nombre de nombres premiers primoriels trouvés.
- La variable i, initialisée à 3, représente le nombre testé.
- Tant que le compteur cp est inférieur à n :
La procédure vérifie si i est un nombre premier primoriel en utilisant la fonction test_premier_primoriel.
Si le test est positif, i est affiché et le compteur est incrémenté.
La valeur de i est ensuite augmentée afin de tester le nombre suivant.
- La recherche s’arrête dès que n nombres premiers primoriels ont été trouvés.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Procedure rechercher_nombres_premier_primoriels(n:entier) Ecrire('Les', n, 'nnombres premiers primoriels sont : ') cp <- 0 # Compteur de nombres trouvés i <- 3 # Début de la recherche à partir de 3 # Continuer la recherche jusqu'à trouver n nombres Tant que cp < n faire Si test_premier_primoriel(i) alors Ecrire(i,' ') cp <- cp + 1 Fin si i <- i + 1 Fin tant que Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| cp | entier |
| i | entier |
Solution en Python
|
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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
# -------------------------------------------------- # Fonction qui permet de saisir un entier n # strictement compris entre inf et sup # -------------------------------------------------- def saisie(inf, sup): # Demande à l'utilisateur de saisir un entier n n = int(input('donner n tel que ' + str(inf) + '< n < ' + str(sup) + ': ')) # Répéter la saisie tant que n n'appartient pas à l'intervalle ]inf, sup[ while (n <= inf) or (n >= sup): n = int(input('donner n tel que ' + str(inf) + '< n < ' + str(sup) + ': ')) # Retourner la valeur valide saisie return n # -------------------------------------------------- # Fonction qui teste si un entier n est un nombre premier # -------------------------------------------------- def test_premier(n): i = 2 # Cas particulier : 2 est premier if n != 2: # Tester la divisibilité de n par les entiers de 2 à n//2 while (i < n // 2) and (n % i != 0): i = i + 1 # Retourne True si aucun diviseur n'est trouvé return (n % i != 0) else: return True # -------------------------------------------------- # Fonction qui calcule le factoriel d’un entier n # -------------------------------------------------- def factoriel(n): f = 1 # Calcul de n! = 1 × 2 × ... × n for i in range(1, n + 1): f = f * i # Retourner la valeur du factoriel return f # -------------------------------------------------- # Fonction qui teste si n est un nombre premier factoriel # -------------------------------------------------- def test_premier_factoriel(n): # Vérifier d'abord si n est premier if test_premier(n): i = 2 f = 1 # Calculer les factoriels successifs jusqu'à dépasser n # et vérifier si n = F! + 1 ou n = F! - 1 while (n != f - 1) and (n != f + 1) and ((f + 1) <= n): f = factoriel(i) i = i + 1 # Retourner True si n est égal à F! ± 1 return (n == f - 1) or (n == f + 1) else: return False # -------------------------------------------------- # Fonction qui teste si n est un nombre premier primoriel # -------------------------------------------------- def test_premier_primoriel(n): # Vérifier d'abord si n est premier if test_premier(n): i = 2 p = 1 # Calculer les produits des nombres premiers successifs (primorielle) # et vérifier si n = P# + 1 ou n = P# - 1 while (n != p - 1) and (n != p + 1) and ((p + 1) <= n): # Multiplier uniquement par les nombres premiers if test_premier(i): p = p * i i = i + 1 # Retourner True si n est égal à P# ± 1 return (n == p - 1) or (n == p + 1) else: return False # -------------------------------------------------- # Procédure qui affiche les n premiers nombres premiers factoriels # -------------------------------------------------- def rechercher_nombres_premier_factoriel(n): print('Les', n, 'nombres premiers factoriels sont :') cp = 0 # Compteur de nombres trouvés i = 3 # Début de la recherche à partir de 3 # Continuer la recherche jusqu'à trouver n nombres while cp < n: if test_premier_factoriel(i): print(i, end=' ') cp = cp + 1 i = i + 1 # -------------------------------------------------- # Procédure qui affiche les n premiers nombres premiers primoriels # -------------------------------------------------- def rechercher_nombres_premier_primoriels(n): print('\nLes', n, 'nombres premiers primoriels sont :') cp = 0 # Compteur de nombres trouvés i = 3 # Début de la recherche à partir de 3 # Continuer la recherche jusqu'à trouver n nombres while cp < n: if test_premier_primoriel(i): print(i, end=' ') cp = cp + 1 i = i + 1 # -------------------------------------------------- # Programme principal # -------------------------------------------------- # Saisie du nombre n (1 < n < 6) n = saisie(1, 6) # Affichage des n premiers nombres premiers factoriels rechercher_nombres_premier_factoriel(n) # Affichage des n premiers nombres premiers primoriels rechercher_nombres_premier_primoriels(n) |
Exécution du programme
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
