Un nombre premier est un entier naturel supérieur ou égal à 2, qui n’a que deux diviseurs : 1 et lui-même.
Étapes de l’algorithme :
- Prendre un entier naturel (n) ((n geq 2)).
- Pour chaque entier (d) allant de 2 à (n-1) (ou jusqu’à la racine carrée de (n)), effectuer :
- Si (n) est divisible par (d) (c’est-à-dire (n % d = 0)), alors (n) n’est pas premier.
- Si aucun diviseur (d) n’est trouvé, alors (n) est premier.
Optimisation :
Il suffit de tester les diviseurs de 2 à (sqrt{n}).
Exemple :
- (n = 13) : testons les diviseurs potentiels 2, 3. Aucun ne divise 13. Donc, 13 est premier.
- (n = 15) : 15 est divisible par 3 (car 15 = 3 × 5). Donc, 15 n’est pas premier.
Algorithme en pseudo-code :
Entrée : n (entier naturel ≥ 2)
Si n = 2 alors
afficher 'n est premier'
Sinon
Pour d de 2 à racine de n incluse
Si n % d = 0 alors
afficher 'n n’est pas premier'
arrêter
afficher 'n est premier'Ce type d’algorithme permet d’explorer la notion d’entiers premiers et de comprendre la méthode de recherche des diviseurs.
