Le programme suivant permet de vérifier sur une calculatrice HP-15C, si un nombre est premier ou pas :

   000 {             }

# ------------------------------------------------------------------------------
   001 {    42 21 11 } f LBL A
   002 {       44  0 } STO 0
   003 {       42 44 } f FRAC
   004 {    43 30  0 } g TEST x≠0
   005 {       22  2 } GTO 2

# ------------------------------------------------------------------------------
   006 {           1 } 1
   007 {       45  0 } RCL 0
   008 {       43 10 } g x≤y
   009 {       22  2 } GTO 2

# ------------------------------------------------------------------------------
   010 {       45  0 } RCL 0
   011 {           2 } 2
   012 {       44 25 } STO I
   013 {    43 30  5 } g TEST x=y
   014 {       22  1 } GTO 1

# ------------------------------------------------------------------------------
   015 {          36 } ENTER
   016 {          36 } ENTER
   017 {       45  0 } RCL 0
   018 {          36 } ENTER
   019 {          33 } R↓
   020 {          34 } x↔y
   021 {          10 } ÷
   022 {       43 44 } g INT
   023 {          20 } ×
   024 {          30 } -
   025 {       43 20 } g x=0
   026 {       22  0 } GTO 0

# ------------------------------------------------------------------------------
   027 {       45  0 } RCL 0
   028 {          11 } √x̅
   029 {       44  1 } STO 1
   030 {           1 } 1
   031 {       44 25 } STO I

# ------------------------------------------------------------------------------
   032 {    42 21  3 } f LBL 3
   033 {           2 } 2
   034 {    44 40 25 } STO + I
   035 {       45  1 } RCL 1
   036 {       45 25 } RCL I
   037 {    43 30  7 } g TEST x>y
   038 {       22  1 } GTO 1
   039 {          36 } ENTER
   040 {          36 } ENTER
   041 {       45  0 } RCL 0
   042 {          36 } ENTER
   043 {          33 } R↓
   044 {          34 } x↔y
   045 {          10 } ÷
   046 {       43 44 } g INT
   047 {          20 } ×
   048 {          30 } -
   049 {    43 30  0 } g TEST x≠0
   050 {       22  3 } GTO 3

# ------------------------------------------------------------------------------
   051 {    42 21  0 } f LBL 0
   052 {       45  0 } RCL 0
   053 {       45 25 } RCL I
   054 {       43 32 } g RTN

# ------------------------------------------------------------------------------
   055 {    42 21  1 } f LBL 1
   056 {       45  0 } RCL 0
   057 {           1 } 1
   058 {       43 32 } g RTN

# ------------------------------------------------------------------------------
   059 {    42 21  2 } f LBL 2
   060 {       45  0 } RCL 0
   061 {    43  4  9 } g SF 9
   062 {       43 32 } g RTN

Utilisation

On place un nombre dans le premier registre de la pile opérationnelle. Puis on lance le programme avec f LBL A :

• si le nombre est premier, la calculatrice affiche 1;
• si le nombre est composé, la calculatrice affiche le premier diviseur trouvé;
• si le nombre n'est pas un entier strictement plus grand que 1, le programme s'arrête immédiatement et l'affichage clignote.

Exemples :

• 97 → 1. Interprétation : 97 est un nombre premier;
• 187 → 11. Interprétation : 187 est un nombre composé divisible par 11;
• 5243,2 → 5243,2 clignotant : le nombre de départ n'est pas conforme.

À la fin de l'exécution, le nombre de départ est aussi placé dans le deuxième registre de la pile, pour un éventuel rappel.

Le programme est long de 62 lignes. La seule optimisation que l'on se permet ici est de tester dés le début la parité du nombre fourni, pour que la boucle principale ne cherche plus que des diviseurs impairs.

Malgré un algorithme naïf, la plupart des calculs sur une HP 15c CE sont raisonnablement rapides :

• 6 700 417 est déjà un joli nombre premier et demande 13 s de traitement.
• 1 999 999 973 est un nombre premier qui demande 3 min 44 s de calculs.
• 9 999 999 967 est le plus grand nombre premier que peut afficher et vérifier cette calculatrice. Il demande 8 min et 19 s de calculs. La boucle principale est parcourue environ 100 fois par seconde (√(9 999 999 967)/2/499). Autrement dit, on teste 100 diviseurs impairs par seconde.

Détails du programme

• Les lignes 3 à 9 testent si le nombre de départ est bien un entier strictement plus grand que 1.
• Les lignes 10 à 13 testent si le nombre est le nombre premier 2. Si c'est le cas, les lignes 55 à 58 affiche 1.
• Les lignes 14 à 26 testent si le nombre est pair. Si c'est le cas, les lignes 51 à 54 affiche 2.
• Les lignes 2 et 27 à 31 initialisent le processus de division par les impairs. On stocke le nombre de départ dans le registre 0, sa racine carrée dans le registre 1 et 1 dans le registre I.
• Le cœur du programme, la boucle, occupe les lignes 32 à 50. On teste les restes des divisions par les nombres impairs consécutifs contenus dans le registre I. Si I dépasse la racine carrée du nombre de départ, c'est que le nombre est bien premier, et on affiche 1 (lignes 55 à 58). Si I divise l'entier de départ, c'est que le nombre est composé et on affiche le diviseur I (lignes 51 à 54). Si aucune de ces conditions n'est remplie, on boucle sur l'impair suivant.
• Les lignes 51 à 62 affichent les résultats.

Précision de l'algorithme

Le test de divisibilité est une partie cruciale du programme :

   036 {       45 25 } RCL I
   039 {          36 } ENTER
   040 {          36 } ENTER
   041 {       45  0 } RCL 0
   042 {          36 } ENTER
   043 {          33 } R↓
   044 {          34 } x↔y

# ------------------------------------------------------------------------------
   045 {          10 } ÷
   046 {       43 44 } g INT
   047 {          20 } ×
   048 {          30 } -
   049 {    43 30  0 } g TEST x≠0

Jusqu'à la ligne 44, pour un diviseur donné, on remplit la pile avec les valeurs nécessaires pour calculer le reste de la division euclidienne du nombre de départ par le diviseur. Les lignes 45 à 48 font le calcul : r=n-int(n/i)*i. Si le reste n'est pas nul, on reprend avec la valeur suivante des diviseurs impairs. Si le reste est nul, c'est que l'on a trouvé un diviseur et on l'affiche.

Pourquoi prendre la peine de calculer le reste ? Ne peut-on pas simplement tester la partie décimale du résultat de la division de n par i ? Et bien, non. Plus exactement, cette dernière méthode n'est pas assez précise pour les très grands nombres, supérieurs à 2×10⁹. Les nombres à dix chiffres sur HP-15C sont arrondis. Quand on teste la partie décimale du résultat de la division, en raison de l'affichage limité à 10 chiffres, des arrondis gênants peuvent arriver.

Exemple : on veut tester la parité de 2 000 000 001. On divise ce nombre par 2 : le résultat réel est 1 000 000 000,5. La machine n'affichant que 10 chiffres, elle arrondit ce résultat au nombre entier 1 000 000 001, dont la partie décimale est 0. On en déduirait, avec erreur, que 2 000 000 001 est divisible par 2...

Soyons astucieux et utilisons des critères de divisibilité pour traiter la divisibilité par 2, 3, 5 et 7. Puis testons la divisibilité par les autres nombres impairs, en commençant au premier nombre premier suivant, à savoir 11, avec la même méthode, à savoir l'examen de la partie décimale de la division du nombre de départ. Aura-t-on réglé définitivement le problème ? Et bien, toujours pas. Les tests de divisibilité par les autres nombres impairs que 3, 5 et 7 peuvent retomber dans les mêmes problèmes d'arrondi du dernier chiffre.

Exemple : on veut tester si 9 999 999 967 est un nombre premier. Ce nombre est plus grand que 2×10⁹. Imaginons que l'on ait réglé la question des tests de divisibilité par 2, 3, 5 et 7 à l'aide de critères de divisibilité (ils sont tous assez faciles à programmer). Au moment de tester la divisibilité de ce nombre par 33, le problème d'arrondi se repose. En effet :

Mais la calculatrice affiche le résultat arrondi 303030302,0, dont la partie décimale est 0. Avec la méthode trop brutale de test de la partie décimale, on en déduit, avec erreur, que 9 999 999 967 est divisible par 33...

Voilà pourquoi on s'embête dans le programme présenté plus haut, à calculer le reste. Ce n'est pas l'algorithme le plus court ou le plus rapide, mais c'est le plus sûr.

Il aurait quand même été dommage d'être limité à 2×10⁹ : on n'aurait pas pu vérifier que 9 999 999 967 est bien le plus grand nombre premier à 10 chiffres. Ça aurait été bête, non ?