Les nombres premiers

Un test qui détermine si un nombre entier est premier est appelé « test de primalité ».

Propriété
Soit un entier naturel. Si aucun entier premier inférieur ou égal à autre que 1 ne divise , alors  est un entier premier.

Pour tester si un entier est premier :

1. calculer sa racine carrée  ;
2. tester si  est divisible par tous les entiers naturels  premiers compris entre 2 et .
   Si un de ces entiers divise , alors c’est un diviseur de autre que 1 et , donc  n’est pas premier. Sinon, est premier ;
3. conclure.

Exemple 1
est-il premier ?
On calcule .
La liste des entiers premiers positifs inférieurs à 11 est {2 ; 3 ; 5 ; 7 ; 11}. On teste la divisibilité de 139 par ces nombres.

• 139 n’est pas divisible par 2 ni par 5.
• 3 × 46 = 138 donc 139 n’est pas divisible par 3.
• 7 × 20 = 140 donc 139 n’est pas divisible par 7.
• Enfin, 11 × 12 = 132 et 11 × 13 = 143 donc 139 n’est pas divisible par 11.

Par conséquent, 139 est premier.

Exemple 2
est-il premier ?
On calcule .
La liste des entiers premiers positifs inférieurs à 8 est {2 ; 3 ; 5 ; 7}. On teste la divisibilité de 69 par ces nombres.

• 69 n’est pas divisible par 2.
• Mais 3 × 23 = 69, donc 69 est divisible par 3.

Par conséquent, 69 n’est pas premier.

On peut déterminer à l’aide d’un programme si un entier naturel non nul est premier ou non.

Pour cela, on teste s’il est divisible par un des entiers inférieurs ou égaux à 29. Ainsi, on peut appliquer l’algorithme à tout entier inférieur ou égal à 29² = 841.

Ce programme affiche 1 si l’entier n est premier et 0 sinon.

Quelques précision sur les instructions

• L1 : on définit la liste qui contient les nombres premiers inférieurs ou égaux à 29.
• L3 : l’instruction int permet de transformer le type d’une variable en entier. En effet, pour déterminer le reste d’une division entre deux entiers, il faut deux variables numériques de type entier.
• L6 : la condition de la boucle while est vraie tant qu’on n’a pas trouvé de diviseur à n (test==1) et qu’on n’a pas passé en revue les entiers de la liste L (K<=9) pour savoir s’ils divisent n.
• L8 : l’instruction n%K donne le reste de la division euclidienne de n par K. Si ce reste est égal à 0, alors n est divisible par K et n’est pas un entier.