Algorithme de vérification d’un nombre premier
Plan de tutoriel
1- Principe de l'algorithme
2- Algorithme de de test de primalité d’un entier
3- Programme Python
Principe de l'algorithme
Un nombre premier est un entier naturel supérieur à 1 qui possède exactement deux diviseurs : 1 et lui-même. L’objectif de cet algorithme est de déterminer si un entier n saisi par l’utilisateur est premier ou non.
Tout d’abord, la fonction saisie() demande à l’utilisateur de saisir un entier supérieur à 1. Une boucle permet de répéter la saisie tant que la valeur introduite n’est pas valide.
Ensuite, la fonction test_premier(a) recherche un éventuel diviseur de a. Elle commence par tester le diviseur 2, puis augmente progressivement la valeur de i. À chaque étape, l'opérateur MOD permet de vérifier si a est divisible par i :
si a MOD i = 0, alors i est un diviseur de a et a n’est pas premier ;
si aucun diviseur n’est trouvé, alors a est premier.
Le programme principal appelle la fonction test_premier(n) et affiche ensuite le résultat : « n est premier » ou « n est non premier ».
Ainsi, l’algorithme repose principalement sur la recherche d’un diviseur de l’entier saisi.
Algorithme de de test de primalité d’un entier
Algorithme du programme Principal
L’algorithme principal PREMIER permet de déterminer si un entier n saisi par l’utilisateur est un nombre premier ou non.
Il commence par appeler la fonction saisie() afin de demander un entier n supérieur à 1. Ensuite, il appelle la fonction test_premier(n) qui vérifie si n est premier et retourne Vrai si c’est le cas, sinon Faux.
Enfin, selon le résultat obtenu, l’algorithme affiche « n est premier » lorsque n est premier, ou « n est non premier » dans le cas contraire.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Algorithme PREMIER Debut # Appeler la fonction saisie() pour demander # et récupérer le premier entier a supérieur à 1. n <-- saisie() # La fonction test_premier retourne : # - Vrai : si n est premier # - Faux : si n n'est pas premier. Si test_premier(n) alors # Afficher un message indiquant que n est premier. Ecrire(n, "est premier") Sinon # Afficher un message indiquant que n n'est pas premier. Ecrire(n, "est non premier") Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction saisie
La fonction saisie() permet de saisir et de contrôler un entier n. Elle oblige l’utilisateur à entrer une valeur strictement supérieure à 1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Fonction saisie():entier Début # La variable test permet de contrôler # la validité de la valeur saisie par l'utilisateur. test <-- Faux # Répéter la saisie tant que la valeur de n # n'est pas supérieure à 1. Tant que test = Faux faire # Demander à l'utilisateur de saisir un entier n. Ecrire("donner n>1 : ")) Lire(n) # Vérifier que la valeur saisie est supérieure à 1. Si n > 1 alors # La valeur saisie est correcte. # On change test à True pour arrêter la boucle. test <-- True Fin si Fin Tant que # Retourner la valeur de n au programme principal. Retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction test_premier
La fonction test_premier(a) permet de déterminer si un entier a est un nombre premier.
Elle commence par traiter le cas particulier où a = 2, qui est un nombre premier. Pour les autres valeurs, elle recherche un éventuel diviseur de a, en testant successivement les entiers à partir de 2.
À la fin de la recherche :
- si aucun diviseur n’est trouvé, la fonction retourne Vrai ;
- si un diviseur est trouvé, elle retourne Faux.
|
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 test_premier(a:entier):booléen Début # Si a est égal à 2, alors a est premier. # En effet, 2 est le premier nombre premier. Si a == 2 alors # Retourner Vrai pour indiquer que a est premier. retourner Vrai Sinon # Initialiser i à 2. # i représente le diviseur que l'on va tester. i <-- 2 # Rechercher un diviseur de a. # # La boucle continue tant que : # - a n'est pas divisible par i # - et i est inférieur à a // 2. # # Si a est divisible par i, la boucle s'arrête. Tant que ((a MOD i != 0) and (i < a Div 2)): # Passer au diviseur suivant. i <-- i + 1 Fin tant que # Après la boucle, vérifier si a n'est pas divisible par i. Si (a MOD i != 0) alors # Aucun diviseur n'a été trouvé. # On considère donc que a est premier. Retourner Vrai Sinon # Un diviseur de a a été trouvé. # a n'est donc pas un nombre premier. retourner Faux Fin si Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
Programme 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 |
# ========================================================== # Fonction de saisie # ========================================================== def saisie(): # La variable test permet de contrôler # la validité de la valeur saisie par l'utilisateur. # Au début, test vaut False car la saisie n'est pas encore validée. test = False # Répéter la saisie tant que la valeur saisie # n'est pas correcte. while test == False: # Demander à l'utilisateur de saisir un entier n. n = int(input("donner un entier n>1 : ")) # Vérifier que la valeur saisie est strictement # supérieure à 1. if n > 1: # La valeur saisie est correcte. # On affecte True à test afin d'arrêter la boucle. test = True # Retourner la valeur de n au programme principal. return n # ========================================================== # Fonction test_premier # ========================================================== def test_premier(a): # Si a est égal à 2, alors a est premier. # En effet, 2 est le premier nombre premier. if a == 2: # Retourner True pour indiquer que a est premier. return True else: # Initialiser i à 2. # i représente le diviseur que l'on va tester. i = 2 # Rechercher un diviseur de a. # # La boucle continue tant que : # - a n'est pas divisible par i # - et i est inférieur à a // 2. # # Si a est divisible par i, la boucle s'arrête. while ((a % i != 0) and (i < a // 2)): # Passer au diviseur suivant. i = i + 1 # Après la boucle, vérifier si a n'est pas divisible par i. if (a % i != 0): # Aucun diviseur n'a été trouvé. # On considère donc que a est premier. return True else: # Un diviseur de a a été trouvé. # a n'est donc pas un nombre premier. return False # ========================================================== # Programme principal # ========================================================== # Appeler la fonction saisie() pour demander # et récupérer un entier n supérieur à 1. n = saisie() # La fonction retourne : # - True : si n est premier # - False : si n n'est pas premier. if test_premier(n): # Afficher un message indiquant que n est premier. print(n, "est premier") else: # Afficher un message indiquant que n n'est pas premier. print(n, "est non premier") |
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
