Test de primalité : Algorithme optimisé par divisions

Pour prouver qu'un nombre A est premier ou pas, la première idée est d'utiliser la définition des nombres premiers. Pour cela il suffit de tester si ce nombre est divisible par un nombre qui lui est inférieur, et de vérifier si le résultat est un entier. Cet algorithme naïf au premier abord, peut conduire à une généralisation intéressante. Voyons cela progressivement.

En toute naïveté, on divise donc A par tous les nombres qui lui sont inférieurs. Soit par 2, 3, 4, 5, etc. Pour aller un peu plus vite faisons quelques raisonnements :

• La liste des nombres n'a pas besoin d'aller jusqu'à A-1, mais seulement jusqu'à la racine carré de A.
  En effet, si A n'est pas premier alors il se compose d'un produit de deux nombres, soit A = N * M, avec nécessairement une relation d'ordre, disons N ≤ M. Or, si N > A^½ alors M > A^½, par conséquent N * M > A, ce qui est absurde puisqu'on a N * M = A.
• Une autre remarque concerne la multiplicité. On sait que tout nombre pair est divisible par 2.
  Par conséquent, si A n'est pas divisible par 2 alors il est inutile de continuer d'essayer avec les multiples de 2, ce qui réduit de moitié le nombre de tests. Cette dernière remarque se généralise avec 3, 5, 7, etc. et on retrouve ici le crible d'Eratosthène.

En d’autres termes, tester si A est premier consiste à essayer de diviser A qu'avec les nombres premiers inférieurs ou égaux à la racine carré de A. Ce qui constitue, en réalité, un optimum au point de vue de la vitesse pour cet algorithme. Néanmoins, cela suppose qu'on connaisse la liste des nombres premiers. Hélas, obtenir cette liste peut demander beaucoup de calculs préalables. C’est tout l’enjeu : comment éviter cela ?

Un compromis simple consiste à utiliser une formule qui évitera de choisir un trop grand nombre de nombres inutiles. Par exemple, pour éviter les nombres multiples de 2 et 3 à la fois, il suffira d'utiliser les nombres générés par les formules 6n+1 et 6n+5, avec n≥1 et entier. Ainsi, on essayera de diviser A par 2, 3 et 5, puis par les nombres générés par les formules, soit par 7, 11, 13, 17, 19, 23, 25, 29 etc. Cette dernière remarque est assez connue, mais personne ne propose sa généralisation… C’est pourtant cette généralisation qui optimise considérablement cet algorithme.

Généralisation : formulations excluant certains multiples

Les formules 6n+1 et 6n+5, excluent les multiples de 2 et 3 à partir de n≥1. Pour généraliser ces formules, par exemple avec 2, 3 et 5 exprimées sous la forme an+b, on procéde ainsi :

• Pour obtenir "a" il suffit de multiplier les trois multiples retenus ici 2, 3 et 5, soit a = 2*3*5 = 30.
• Pour obtenir les différentes valeurs de "b", il suffit d'écrire la suite des nombres compris entre 30 (=1*a) et 60 (=2*a), et de supprimer les multiples de 2, 3 et 5 auxquelles on retranchera "a".
  Donc, ici on obtient la suite {31, 37, 41, 43, 47, 49, 53, 59}, soit b= {1, 7, 11, 13, 17, 19, 23, 29}. En réalité, il est également possible de généraliser la constitution systématique de la liste des valeurs de "b".

Maintenant, pour tester plus rapidement par divisions la primalité d'un nombre A, on le divisera par les premiers nombres premiers inférieurs à 30, soit par {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, puis par les valeurs obtenues avec 30n+b, avec n≥1 et "b" constitué des 8 valeurs ci-dessus, et sans dépasser la racine carré de A.

En programmation

Informatiquement, on constate que pour un nombre de type Double, on optimise le procédé en supprimant uniquement les multiples 2, 3, 5, 7, 11 et 13, soit a=30030 et b est alors constitué de 5627 valeurs. En termes de performance, on peut tester la borne entière du type Double, soit 999999999989 donc un nombre de 12 chiffres en 8 millisecondes sur un PC à 2 GHz. Remarquable performance, non ?

Vous pouvez tester par vous-même grâce à mon petit programme écrit sous VB2008 mettant en œuvre les présentes explications (téléchargement). Pour récupérer le code source cliquer ici.