Hace un tiempo, leyendo el fantástico libro
Perl One-Liners: 130 Programs That Get Things Done de Peteris Krumins, me encontré con una expresión regular que chequea si un número dado es primo
.
En realidad, chequea si es compuesto siendo el test de primalidad de la forma
unario($candidato_a_primo) !~ $regex (o sea, da por primo un entero sii un
string de unos formado a partir de él mediante la función
unario(),
NO verifica cierta expresión regular).
La expresión regular aparentemente es de la autoría del famoso
Perl hacker alemán Abigail (del cual se desconoce en realidad si es una mujer: hay foros que hablan de
él y otros de
ella), y apareció en Internet por primera vez en 1998. Abigail es un personaje enigmático en la comunidad Perl y se hizo muy conocido/a a partir de sus brillantes programas JAPHs, así como por su genial destreza con las expresiones regulares. (Un programa JAPH es un programa que imprime en la salida estándar el texto "Just another Perl hacker," de la forma más críptica posible, tal como lo hace el programa que está en mi firma, que se me ocurrió un día que estaba aburrido
).
Suponiendo que el candidato a primo está en la variable
$_, el test de primalidad es el siguiente:
(1x$_) !~ /^1?$|^(11+?)\1+$/La idea es extremadamente sencilla, pero de una belleza y creatividad inusitadas. Hay quienes han tenido problemas en desentrañar cómo es que la anterior expresión regular funciona; en mi caso, capté la idea antes de leer la explicación en el libro, y reitero, que la idea es muy sencilla y muy bella. Pongo la explicación en el Spoiler para dar la oportunidad a que lo piensen antes de ver la solución.
Explicación
Primero que nada, se convierte el número a su representación unaria con 1x$_, que no es otra cosa que el string "1" concatenado consigo mismo tantas veces como $_, que es el número cuya primalidad queremos determinar. Por ejemplo, si $_ vale 5, 1x$_ será el string "11111". La idea detrás es la siguiente: si el número es compuesto, entonces es posible descomponer esa cadena de unos en subcadenas de unos de igual tamaño. Por ejemplo, si el número es 4, entonces "1111" puede descomponerse como "11"."11" lo que puede interpretarse como \( 4=2\times 2 \) (el primer 2 es la cantidad de subcadenas, y el segundo 2 la longitud de las mismas). Si es 6, entonces "111111" es "111"."111" (\( 3\times 2 \)) o también "11"."11"."11" (\( 2\times 3 \)).
Luego la expresión regular tiene dos partes: la primer parte es ^1?$ que matchea "1" y el string vacío. Ninguno de éstos es un número primo así que esa parte de la regexp los descarta. La segunda parte, ^(11+?)\1+$ chequea si una subcadena de 2 o más unos (que es capturada con los paréntesis) repetida una o más veces, determina la representación unaria entera. Si se cumple esa condición, el número es compuesto o de lo contrario, es primo.
Por ejemplo, para el caso del número 5, su representación unaria es "11111" entonces (11+?), como el cuantificador +? es non-greedy, captura inicialmente "11" y la backreference \1 queda conteniendo "11" luego toda la expresión regular se transforma en ^11(11)+$. Como "11111" no matchea esta expresión regular, falla. A continuación, el motor de expresiones regulares prueba avanzar un "1" más en la captura de (11+?), o sea, ahora captura "111" y \1 queda con "111". La expresión regular se vuelve ^111(111)+$, que también falla. Luego continúa el backtracking capturando "1111" y "11111", fallando en ambos casos. Como fracasa con todas las posibles capturas, "11111" no matchea la regexp y se concluye que 5 es primo.
Si están en un SO basado en Unix, pueden probar esta expresión regular de esta manera:
$ perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ es primo"'La opción
-n pone cada línea de la entrada estándar en
$_ de manera que cuando presionen enter,
perl quedará esperando a que introduzcan un número para evaluar la condición. Una vez que terminen de "jugar", pueden presionar ^C para enviare la señal SIGINT al proceso e interrumpir su ejecución, o bien ^D (carácter EOF). También pueden usar un
pipe | para conectar la salida de un programa con la entrada de otro. Por ejemplo,
$ perl -le 'print for 1..100' | perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ es primo"'
2 es primo
3 es primo
5 es primo
7 es primo
11 es primo
13 es primo
17 es primo
19 es primo
23 es primo
29 es primo
31 es primo
37 es primo
41 es primo
43 es primo
47 es primo
53 es primo
59 es primo
61 es primo
67 es primo
71 es primo
73 es primo
79 es primo
83 es primo
89 es primo
97 es primo
