Test de primalité avec les expressions régulières

Bonjour,

Je suis tombé par hasard sur une méthode amusante
utilisant les expressions régulières pour tester si un nombre
est premier. Je vous la soumets.

Voici le code (en python)

--------------------------------------------
import re

def is_prime(n):
return not re.match(r"(..+?)\1+", "1"*n)
--------------------------------------------

Difficile de faire un test de primalité plus concis ;)

Quelques explications.

La "string": "1"*n:

Le '1'*n produit une chaine avec n "1" consécutifs,
ex si n=6 -> "111111" , et on va tester si le nombre de
caractères de cette chaine est premier ou pas.

Le "pattern": (..+?)\1+

Le point "matche" un caractère quelconque (ici ce sera les 1 de
la chaine), le + veut dire "répété une fois ou plus, et le ? veut
dire "lazy" (fainéant, le moins possible), les ( ) entrainent une
mémorisation et le \1 rappelle ce qui a été mémorisé.

Comment ça marche ?

Comme le 1er + est lazy, il commence par répéter une seule fois le
caractère qui précède, donc on a (..) dans la parenthèse
qui va matcher "11" de la string, le "11" est mémorisé puis on
le rappelle avec le \1. On a donc "1111" comme pattern puis le \1
est répété une fois ou plus (avec le dernier +) en mode "greedy"
(glouton) cette fois.
Le moteur regex tente donc de matcher la string avec

1111 ou
111111 ou
11111111 ou
etc

S'il y arrive c'est que la longueur de la string est multiple de 2,
(sauf pour 2) donc non premier, et la fonction is_prime retourne
False. (Si la string est de longueur 2, les matches échouent)

S'il n'y arrive pas, le moteur regex fait du backtracking, le premier
+ (lazy) répète maintenant 2 fois le caractère qui précède, le contenu
de la parenthèse devient (...) , le moteur regex tente donc de matcher
la string avec

111111
111111111
111111111111
etc

S'il y arrive c'est que la longueur de la string est multiple de 3,
(sauf pour 3) donc non premier, et la fonction is_prime retourne
False. (Si la string est de longueur 3, les matches échouent)

Avec une string de longueur un nombre premier, ça s'arrête quand
le premier + ne peut plus augmenter le nombre de caractère à
l'intérieur de la ( ) car on dépasse en taille la string.
Dans ce cas le match échoue et la fonction retourne True.

Si la longueur n'est pas premier, il y aura un match et la fonction
retournera False

La fonction ne marche pas avec n=0 ou 1 (elle retourne True, premier),
une simple modif de la l'expression régulière permet de palier à ce problème.

https://iluxonchik.github.io/regular-expression-check-if-number-is-prime/