Nombre premier et test de primalité.

Un nombre est premier si il n'a que deux diviseurs, 1 et lui même.
Le chiffre est 1 n'est donc pas premier et 2 est le seul entier pair qui soit premier.

Les deux questions immédiates que l'on peut se poser sont comment savoir si est un nombre entier est premier et à quoi servent les nombres premiers ?
Il existe divers tests de primalité, des plus simplistes (comme celui présenté) aux tests probabilistes et déterministes.
Les nombres premiers ont de nombreuses applications notamment dans le domaine de la cryptographie pour les algorithmes de chiffrement comme le RSA dont nous reparlerons bien sûr dans un prochain article.

Revenons à notre algorithme déjà vu en juillet dernier avec la HP-35S.
Nous allons rechercher si un nombre entier supérieur ou égal à 3 est un nombre premier en utilisant l'algorithme de test élémentaire suivant:

Si ( N est Pair)  Alors ( N est non Premier - Fin du Test)
K = 3
Début Test
{
    Si ( K > RacineCarrée( N ) ) Alors ( N est Premier - Fin du Test )
    Si ( K divise N ) Alors ( N est non Premier - Fin du Test ) 
    K = K + 2
}
Retourne Début Test

Pour faire simple on teste si N est pair, si tel est le cas N n'est pas premier sinon on teste si la racine carrée de N est divisible par un nombre impair. Si ce n'est pas le cas, N est premier.

Voici le programme associé qui renvoie 1 si le nombre est premier et 0 si il n'est pas premier.

<< DUP √ FLOOR 3 ⟶ N M I
  << 1 SF
     IF N 2 MOD NOT
     THEN 1 CF
     END
     WHILE 1 FS? I M ≤ AND
     REPEAT
       IF N I MOD
       THEN 2 'I' STO+
       ELSE 1 CF
       END
     END 1 FS?
  >>
>>

Enregistrez et utilisez ce programme comme de coutume, le seul argument est le nombre à tester qui doit être sur la dernière ligne du stack (je n'indiquerai plus comment enregistrer et utiliser un programme avec la HP-50G à partir de maintenant, veuillez vous référer aux articles précédents si besoin).

Voici quelques nombres à tester: 403 est non premier, 997 est premier, 2603 est non premier et 524287 est premier.

Bien sûr cet algorithme n'est jamais utilisé en pratique car pour de grands nombres vous pouvez aller prendre un verre pendant que la 50G va procéder à la recherche ;-)
La calculatrice dispose de la fonction ISPRIME en natif et vous pouvez comparer les temps d'exécutions entre notre algorithme très "scolaire" et celui qu'utilise la calculatrice.

Je présenterai très prochainement le plus simple des tests probabilistes, celui de Fermat (le petit théorème de Fermat est étudié en terminale S spé Maths) pour tester la primalité (supposée) de très grands nombres.

Liens intéressants:
Les divers tests de primalité.

A bientôt !