228 meneos
5144 clics

Desmitificando la expresión regular que comprueba si un número es primo [ENG]

¿Alguna vez te has preguntado por qué la expresión regular ^.?$|^(..+?)1+$ comprueba si un número es primo? En este artículo se explica cómo y porqué funciona. (Artículo extenso en inglés)
etiquetas: expresion regular, informatica, programacion, primo, matematicas
usuarios: 111   anónimos: 117   negativos: 3  
Comentarios destacados:                   
#29   #7 Lo que hace es (de forma críptica e ineficiente en una linea) apoyarse en que las expresiones regulares realmente son funciones que hacen un trabajo bestial (con bucles internos), para hacer ese primer método clásico que se a todos se nos ocurre para calcular los primos, es decir, dividir entre 2,3,4,... y comprobar si es divisible, y si no lo es, entonces es primo.

Paso 1: Convertir el número a una cadena de la longitud del número. Por ejemplo 15 lo convertimos en "xxxxxxxxxxxxxxx".
Paso 2: Por medio de una expresión regular comprobar si "xxxxxxxxxxxxxxx" se puede dividir en bloques iguales, tipo "xxx"+"xxx"+"xxx"+"xxx"+"xxx", sin que sobre ninguna "x". La expresión regular se esfuerza en encajar el string en varios bloques de un mismo número de elementos, y responde true si lo consigue.
Paos 3: Si devuelve true, es que no es primo. Si devuelve false, es que es primo.
#1   Me lo pregunto todos los días, hoija.
votos: 8    karma: 57
#37   #1 Tampoco hace falta presumir de desinterés digo yo...
votos: 15    karma: 98
#2   Resumen rápido: es primo si
a) no es cero o uno.
b) es una cantidad mayor de dos repetida dos o más veces.
votos: 4    karma: 47
#4   #2 Gráficamente

Edito. Como dice #9, no es cierto. Siento.  media
votos: 0    karma: 17
 *   ángel. ángel.
#9   #4, lo que dice esa imagen es falso. Para n=0, 1, 2, 3 y 4 se cumple. Para n=5 ya no, y no sé si e su existe algún otro caso para el que se cumpla. De hecho esos números son llamados números de Fermat y él mismo conjeturó (erróneamente) que eran todos primos.
votos: 15    karma: 147
 *   zurditorium zurditorium
#10   #9 Pues se agradece el comentario.
votos: 4    karma: 63
#12   #10, he editado añadiendo información.
votos: 1    karma: 32
#14   #12 Gracias
votos: 0    karma: 17
#44   #9 No dice que n sean todos los naturales, sería una explicación de la forma que tienen los números de Fermat, supongo.
votos: 1    karma: -2
#11   #4 Hay muchos más primos aparte de los que es obtienen de esa forma.
votos: 1    karma: 20
#13   #11 hola soy un primo, me obtuvieron de otra forma
votos: 5    karma: 60
#25   #13 ola primo ke ase
votos: 0    karma: 10
#20   #5 En primer lugar, esa fórmula sólo es válida para ciertos valores de n.
En segundo lugar, hay números primos que no cumplen eso.
Entre lo que se lee en #2, #4 y #5, ¿me puedo fiar de los programas informáticos? :-(
votos: 0    karma: 10
#23   #20 ya que dispones de conocimientos que los demás no tienen, se agradecería que fueras tan amable de completar, corregir y/o aclarar el artículo: en.wikipedia.org/wiki/Primality_test
votos: 0    karma: 11
#26   #23 Vale, en #20 había confundido un primo factorial con el teorema de Wilson. Perdón.
Pero, salvo que se me escape algo, lo que pones en #5 no es lo mismo que (n-1)!=-1+n*m
votos: 1    karma: 13
 *   positifo
#17   #2 No, no es eso lo que hace. Si lo hiciera, estaría mal.
Goto #16
votos: 0    karma: 10
#28   #17 Lol
votos: 0    karma: 17
#3   Soy desarrollador, pero que esto llegue a portada de menéame ya me parece pasarse de frikismo.
votos: 25    karma: 215
#15   #3 a veces me pregunto si los que menean las noticias antes de que lleguen a portada son usuarios normales o una panda de trolls :-D
votos: 2    karma: 4
aum
#39   #3 ¿por qué? ¿ha habido alguna otro artículo técnico de divulgación esta semana más merecedor que este de llegar a portada de un agregador de noticias general? Explica lo que es una expresión regular con un buen ejemplo práctico.

#15 Yo me pregunto por que los usuarios que nunca miran los envíos hasta que llegan a portada pero que luego no tienen ningún problema en tirar los que han llegado pueden seguir votando, la verdad. Si no miras lo que no está en portada, ¿cómo puedes saber si lo que hay en portada es bueno o había algo mejor?
votos: 6    karma: 58
#50   #3 ¡Pues está!
votos: 0    karma: 9
#5   Muy inteligente… pero ineficiente. Incluso la fórmula del factorial es más rápida (5 veces más rápida para el caso del número 1997):

n - (factorial(n - 1) % n) == 1
votos: 5    karma: 31
#19   #7 sí que hay fórmulas, lee #5
El problema es el tiempo de computación para números grandes. Te remito a en.wikipedia.org/wiki/Primality_test
votos: 3    karma: 36
#34   #19, eso no son fórmulas, es Có si me dices que probar si un número es divisible por todos los menores a él es una fórmula. Hay formas de ahorrar pasos y que el proceso no sea tan largo, pero eso, que así en general no hay.

CC #16
votos: 2    karma: 49
#42   #34, bueno, la que dice #5 estrictamente hablando sería una fórmula, pero hay que hacer n operaciones, más que probando dividiendo con los menores a su raíz cuadrada (aunque computacionalmente no sé si por el tipo de operación será más rápido).

Por cierto #5, lo has escrito raro, la fórmula que pones es equivalente a

(n-1)! (mod n) = - 1
votos: 0    karma: 18
#56   #42 lo he escrito en lenguaje de programación. Puedes usar C, Java, JavaScript (se puede probar en la consola del navegador)… Lo explico por si no conoces programación:
Asumiendo factorial() como una función ya existente, entonces:
n es el número a probar
factorial(n - 1) es el factorial del número anterior
% es el operador módulo de división entera
== es el operador de igualdad booleana

con lo cual, si todo a la izquierda evalúa 1, significa que el número es primo (la expresión es true)
votos: 0    karma: 11
#79   #56, la fórmula la entiendo. Lo que digo es que has escrito que que hay que calcular módulo n el número

n - (n-1)!

Y yo lo que digo es que basta calcular

(n-1)!


Una operación menos. La diferencia es que en mi caso lo que hay que ver es si es congruente con - 1 (en tu caso con 1).

Es más, solo hay 3 posibilidades, que sea primo y de - 1 o qué no sea primo, y entonces dará 0 salvo en el caso del 4 en el que dará 2.
votos: 0    karma: 18
#81   #79 correcto, y además al ahorrar la resta la fórmula que propones es un 10 % más rápida
mis dies
votos: 0    karma: 11
#83   #81, ¿un 10% más rápida? Lo dudo mucho, la diferencia debe de ser insignificante.
votos: 0    karma: 18
#32   #5 cuidado que la implementación del factorial sin recursión de cola puede mandar la pila al cuerno.
votos: 0    karma: 10
#57   #32 elige: rápido o que consuma poca memoria. Engineering is about trade-offs
votos: 0    karma: 11
#80   #57 Mas bién no. La implementación recursiva normal gasta memoria y encima es mucho más lenta.

Si hablamos de hashes en memoria, pues entonces sí.
votos: 0    karma: 10
 *   Ander_ Ander_
#6   por fin es viernes
votos: 3    karma: 31
#52   #6 mañana es sábado

Deberíamos hacer una canción sobre ello :troll:
votos: 0    karma: 7
#7   No entiendo lo que dice la noticia, pero por si a alguien le sirve, no existe ninguna fórmula ni similar que te diga su un número es primo o no.
votos: 4    karma: 48
#16   #7 Sí, el método a pelo (la criba de Eratóstenes), que parece que es lo que hace ese algoritmo.
votos: 4    karma: 33
#41   #16 Pero agrupando "palitos" para dividir. Es como factorizar con herramientas de la edad de piedra (sin sistema de numeración)
votos: 1    karma: 26
 *   CHN
#29   #7 Lo que hace es (de forma críptica e ineficiente en una linea) apoyarse en que las expresiones regulares realmente son funciones que hacen un trabajo bestial (con bucles internos), para hacer ese primer método clásico que se a todos se nos ocurre para calcular los primos, es decir, dividir entre 2,3,4,... y comprobar si es divisible, y si no lo es, entonces es primo.

Paso 1: Convertir el número a una cadena de la longitud del número. Por ejemplo 15 lo convertimos en "xxxxx…   » ver todo el comentario
votos: 29    karma: 206
 *   fugaz
#36   #29 Sólo una cosa que añadir a tu excelente comentario: realmente esa expresión no es una expresión regular en el sentido formal del término (expresiones que se compilan a un autómata finito y que reconocen un lenguaje regular - los primos no lo son). Lo que pasa es que las implementaciones de expresiones regulares en lenguajes como Perl o Java meten extensiones que les añaden potencia.

La ventaja de esto es que puedes hacer más cosas, el inconveniente es que, como estas expresiones extendidas…   » ver todo el comentario
votos: 12    karma: 88
#64   #29 Joder, me he leído el artículo entero y no lo había entendido de forma tan clara hasta ahora.
votos: 2    karma: 25
#75   #29 Supongo que con un sentido de división de los bloques.

Por ejemplo el 15 que has puesto daría su división a estas secuencias:

3 + 3 + 3 + 3 + 3 (True)

5 + 5 + 5 (True)

7 + 7 + 1 (sobra 1) (false)
votos: 0    karma: 6
 *   jmav
#30   #7 Por tu comentario creo adivinar que necesitarás unos miles de años más estudiando para conseguir tu objetivo de la medalla Fields.
votos: 0    karma: 8
#77   #7 entonces según tu es imposible calcular si un numero es primo
votos: 0    karma: 7
#78   #77, no he dicho eso.
votos: 0    karma: 18
#8   Justo estaba en la tasca ayer preguntame eso mismo con mi amigo Patxi.
votos: 1    karma: 20
#18   #8 Esto mismo no, pero la típica conversación de afterwork perfectamente pude tratar sobre el tamaño optimo del slice para un planificador basado en un sistema de colas multinivel con prioridad variable gestionado por un round robin.
votos: 2    karma: 14
#46   #18 n/2 ? ?(
votos: 0    karma: 6
#21   Hay expresión regular, hay meneo. A fin de cuentas, Menéame puede considerarse como un conjunto de expresiones mediocres, pero con cierta coherencia temporal.
votos: 3    karma: 33
#49   #21 mejor crípticas que no mediocres, al menos por la parte de las expresiones regulares.
votos: 0    karma: 7
 *   PauMarí
#22   Después de ser ser corregido he editado mi comentario advirtiendo de mi error. <:( Lo siento.
votos: 1    karma: 24
#24   Sin lugar a dudas lo hace por fuerza bruta, pero bruta bruta...

Pero es bien curioso =)

Me da la sensación de que fuese de algún problema de CodeFight, porque nadie en su sano juicio creo yo que lo utilizaría en serio... :-P
votos: 2    karma: 34
 *   cucufatefate
#27   Factorial rápido? Cuéntame más.  media
votos: 0    karma: 6
#33   #27 En Scheme puede ser relativamente rápido:

(define (fact x)
(define (fact-tail x accum)
(if (= x 0) accum
(fact-tail (- x 1) (* x accum))))
(fact-tail x 1))

Me saca el factorial de 12345 en 3 segundos.
votos: 2    karma: 27
 *   Ander_ Ander_
#53   #27 No es tan lento si lo implementas bien -> www.luschny.de/math/factorial/Benchmark.html. Aunque todo es relativo, claro.
votos: 0    karma: 6
#31   Cuanto más primo más me arrimo
votos: 0    karma: 7
#35   ¿Alguien sabe cuál es la expresión regular para calcular cuántos de los que han meneado el artículo se lo han leído?
votos: 3    karma: -8
#47   #35 error: texto muy breve o caracteres no válidos
votos: 0    karma: 6
#38   Por cierto, ni se os ocurra usar esta mierda en ningún sitio. Es divertido para aprender pero también un worst programming ever.
Para calcular si el número 10.000.000.001 es primo este método requiere pedir memoria al sistema para un String de 10GB.
votos: 8    karma: 15
 *   fugaz
#40   #38 ¿Y es primo? :troll:
votos: 0    karma: 14
#45   #40 10.000.000.001 Es divisible entre 101.
votos: 1    karma: 21
 *   fugaz
#61   #45 No me fiaba de ti, así que he tenido que comprobarlo.
votos: 0    karma: 6
#85   #61 con una expresión regular? :troll:
votos: 1    karma: 14
#86   #85 No sabría cómo. Y eso que me he leído el artículo.
votos: 0    karma: 7
#43   El artículo es buenísimo para poder entender las expresiones regulares más típicas.
votos: 3    karma: 22
#48   No, la verdad es que nunca me lo había preguntado.
votos: 0    karma: 9
#51   #0 Sé que aparece como tal en algunos diccionarios pero "to demystify" es "aclarar" o "clarificar", no "desmitificar". "To demystify" tiene el sentido de aportar luz a algo desconocido, pero no el de rebajar algo idealizado a la categoría de común que tiene en español.
votos: 4    karma: 41
#60   #51 Gracias. Un falso amigo, vamos.

Que conste que lo he buscado en un diccionario porque me resultaba un poco extraño.
votos: 1    karma: 18
#54   Implementar una expresión regular de ese calibre como en el primer ejemplo es de una maldad que ni un millón de piezas de Lego tiradas por el borde de una piscina.

 media
votos: 3    karma: 46
 *   --174--
#55   TL;DR: el truco está en representar el número a comprobar en formato unario... y usar la expresión regular para ver si la cadena resultante se puede dividir exactamente en un número cualquiera de grupos de longitud igual o menor al total.

Algo así como una forma super-ineficiente de: pastebin.com/8R2rEua9  media
votos: 1    karma: 10
 *   Lb2A3qA Lb2A3qA
#58   #55 Eso no es eficiente :-P con comprobar hasta la raíz cuadrada de el número en cuestión sobra, no hace falta tanto :-P
votos: 0    karma: 12
#71   #58 Estaba explicando cómo funciona lo de la regex, pero si ves una forma de solo comprobar hasta la raíz cuadrada con una regex... adelante o_o
votos: 1    karma: 19
#72   #71 Yo me refería a lo que has puesto como ejemplo :-P ya sé que las expresiones regulares se aplican sobre cadenas de caracteres, no cantidades, por lo que aplicar operaciones aritméticas sobre ellas es "complicado" xD
votos: 0    karma: 12
#59   #55 En tu ejemplo,
número = 4
4%2 == 0 => ¿4 es primo?
votos: 1    karma: 18
#70   #59 Tal vez se me haya olvidado un "no" en el print. Pos bueno, para la versión 2.0 si eso xD
votos: 1    karma: 16
#82   #55 Serás bestia... :palm: Tu algoritmo considera primo cualquier número mayor que 1, o sea cualquiera. Y ni remotamente se parece a la agrupación de cadenas que hace la expresión regular. Además de eficiente no tiene nada, el eficiente para comprobar divisores es O(n1/2) y el tuyo O(n).

Vamos, que te has lucido. Suele pasar con todos los sabihondos que opináis después de admitir que ni os habéis leído el artículo. :roll:
votos: 0    karma: 11
 *   Malversan
#62   Como me encantan las expresiones regulares :-)
votos: 0    karma: 9
#63   Ya era hora, esto era un baño de sangre.
votos: 0    karma: 7
#65   Estamos debatiendo sobre matemáticas y teoría de la programación, pero si alguien necesita de verdad un proceso eficiente para determinar si un número (no excesivamente grande) es primo o no, lo más rápido es tener en RAM la lista del primer millón de números primos (por ejemplo) y buscarlo ahí (no de forma secuencial, por supuesto).
votos: 1    karma: 20
#66   #65 Propongo un algoritmo que cada vez que se usa, vaya guardando los primos obtenidos para usarlos la vez siguiente...
votos: 0    karma: 8
#68   #66 Tu idea solo sería eficiente si por alguna razón, los números candidatos no fueran aleatorios sino que alguno se repitieran con mucha más frecuencia que otros. En ese caso, mantener una caché de primos frecuentes sería una buena estrategia.
votos: 0    karma: 11
#69   #68 Bueno, los primos no estan repartidos de modo uniforme. Cada vez están más separados.

Evidentemente depende del caso, pero en muchas situaciones sí sería eficiente.
votos: 0    karma: 8
#67   En meneame hay mas numeros cuñao
votos: 0    karma: 9
#73   Un desarrollador tiene un problema y decide solucionarlo con expresiones regulares....

Ahora tiene 2 problemas.

xD

No sé quién dijo esa frase, pero q razón...
votos: 3    karma: 32
#74   - ¿Sabe Ud. escribir expresiones regulares?
- No uso expresiones regulares, todas mis expresiones son buenas.

Horrible, y me he logeado solo para contarlo.

Estuve a punto de soltarlo en una entrevista de trabajo, no lo hice, y conseguí el puesto. Moraleja: cómo me dijo mi hermana cuando trajo a su novio por primera vez a casa... por favor, no seas tú mismo.
votos: 2    karma: 24
#76   Las expresiones regulares son el idioma de los primigenios. Cuidado con lo que escribís, no vayáis a despertar a Cthulhu. Yo me la juego cada día, pero no llego a estos niveles xD
votos: 0    karma: 10
#84   Ahora que lo pienso en su momento hice una máquina de turing que básicamente hacía eso mismo, vamos una criba de eratostenes a pelo... Jamás se me habría ocurrido aplicarlo en una expresión regular. Me quito el sombrero ante el que tuviera esa cuestionable idea. xD
votos: 0    karma: 7

menéame