Ce minuscule script Perl d'une seule instruction ( print str =~ regex ? no : yes ) indique par YES ou NO si le l'entier passé en argument sur la ligne de commande est un nombre premier :
#!/usr/bin/perl
#usage: isPrime.pl <entier>
print (('@' x $ARGV[0]) =~ /^.?$|^(..+?)\1+$/ ? "NO\n" : "YES\n");
 |
| Spirale d'Ulam |
Le cœur du script est une expression régulière qui matche quand l'argument n'est pas un nombre premier. Cette expression régulière s'applique à une chaîne de caractères identiques et de longueur égale à la valeur de l'argument.
La chaîne contenant autant de @ qu'indiqué par l'argument est construite avec ('@' x $ARGV[0]).
Exemple: isPrime.pl 6 travaille sur la chaîne "@@@@@@"
La première partie de la regex ^.?$ détermine s'il y a 0 ou 1 caractère dans la chaîne, autrement dit si le nombre à tester est 0 ou 1. Si c'est le cas le nombre n'est pas premier (affiche NO).
La deuxième partie de la regex ^(..+?)\1+$ détermine s'il est possible de décomposer la chaîne en la répétition d'une sous chaîne d'au moins 2 caractères. Si c'est le cas c'est que la longueur de la chaîne (donc la valeur de l'argument) peut s’écrire L * N, (avec L>0 et N>1) et donc le nombre n'est pas premier (affiche NO).
- L est la longueur de (..+?)
- n est le valeur que représente le + dans \1+
Exemples :
- isPrime.pl 9
La chaîne de 9 caractères "@@@@@@@@@" est décomposée en 3 répétitions de "@@@"
==> matche ==> 9 n'est pas un nombre premier. - isPrime.pl 12
La chaîne de 12 caractères "@@@@@@@@@@@@" est décomposée en 6 répétitions de "@@"
==> matche ==> 12 n'est pas un nombre premier. - isPrime.pl 11
La chaîne de 11 caractères "@@@@@@@@@@@" n'est pas décomposable en N répétitions d'une chaîne de longueur L
==> ne matche ==> 11 est un nombre premier.
La classique boucle de cherche les diviseurs d'un nombre est prise en charge par la recherche itérative d'une solution dans le moteur d'expressions régulières. Bien sur la méthode n'est ni efficace en place mémoire ni en temps de calcul, mais elle est originale.
Vous trouverez une liste des 50000 premiers nombres premiers ici.
Note: L'image utilisée pour illustrer ce post est la spirale d'Ulam qui représente la position des nombres premiers sur une spirale. Les lignes droites semblent indiquer une certaine organisation (un pattern) des nombres premiers...intriguant...