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

228 meneos

5296 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)

111 117 3 K 602 tecnología

86 comentarios

111 117 3 K 602 tecnología

Comentarios destacados:

#29 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 borteixo

Me lo pregunto todos los días, hoija.

8 57
#2 --324579--

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.

4 47
#3 Lito

Soy desarrollador, pero que esto llegue a portada de menéame ya me parece pasarse de frikismo.

25 215
#4 Arariel *

#2 Gráficamente

Edito. Como dice #9, no es cierto. Siento.

0 17
#5 ED209

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

5 31
#6 level3

por fin es viernes

3 31
#7 --165145--

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.

4 48
#8 oxelo

Justo estaba en la tasca ayer preguntame eso mismo con mi amigo Patxi.

1 20
#9 --165145-- *

#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.

15 147
#10 Arariel

#9 Pues se agradece el comentario.

4 63
#11 --89367--

#4 Hay muchos más primos aparte de los que es obtienen de esa forma.

1 20
#12 --165145--

#10, he editado añadiendo información.

1 32
#13 kastromudarra

#11 hola soy un primo, me obtuvieron de otra forma

5 60
#14 Arariel

#12 Gracias

0 17
#15 aum

#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

2 4
#16 --89367--

#7 Sí, el método a pelo (la criba de Eratóstenes), que parece que es lo que hace ese algoritmo.

4 33
#17 --89367--

#2 No, no es eso lo que hace. Si lo hiciera, estaría mal.
Goto #16

0 10
#18 empanadilla.cosmica

#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.

2 14
#19 ED209

#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

3 36
#20 --89367--

#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?

0 10
#21 systembd

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.

3 33
#22 Arariel

Después de ser ser corregido he editado mi comentario advirtiendo de mi error. Lo siento.

1 24
#23 ED209

#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

0 11
#24 --481172-- *

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...

2 34
#25 borteixo

#13 ola primo ke ase

0 10
#26 --89367-- *

#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

1 13
#27 frutosm

Factorial rápido? Cuéntame más.

0 6
#28 --324579--

#17 Lol

0 17
#29 fugaz *

#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.

29 206
#30 --408987--

» ver comentario
#31 opinator87

Cuanto más primo más me arrimo

0 7
#32 --125581--

#5 cuidado que la implementación del factorial sin recursión de cola puede mandar la pila al cuerno.

0 10
#33 --125581-- *

#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.

2 27
#34 --165145--

#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

2 49
#35 ommmmm

¿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?

3 -8
#36 Al-Khwarizmi

#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 ya no compilan necesariamente a un autómata finito, puedes estar metiendo sin darte cuenta unas ineficiencias del copón (como esta misma expresión, que hace un cálculo no trivial de una forma tremendamente ineficiente). Una expresión regular "pura" se caracteriza por ser algo muy eficiente en tiempo y memoria, con las extensiones ya no tanto. No es problema para quien sepa lo que está haciendo, claro.

12 88
#37 ccguy

#1 Tampoco hace falta presumir de desinterés digo yo...

15 98
#38 fugaz *

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.

8 15
#39 ccguy

#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?

6 58
#40 Xtrem3

#38 ¿Y es primo?

0 14
#41 CHN *

#16 Pero agrupando "palitos" para dividir. Es como factorizar con herramientas de la edad de piedra (sin sistema de numeración)

1 26
#42 --165145--

#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

0 18
#43 Rydra

El artículo es buenísimo para poder entender las expresiones regulares más típicas.

3 22
#44 pitter

#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.

1 -2
#45 fugaz *

#40 10.000.000.001 Es divisible entre 101.

1 21
#46 BetusPrime

#18 n/2 ?

0 6
#47 BetusPrime

#35 error: texto muy breve o caracteres no válidos

0 6
#48 diskover

No, la verdad es que nunca me lo había preguntado.

0 9
#49 PauMarí *

#21 mejor crípticas que no mediocres, al menos por la parte de las expresiones regulares.

0 7
#50 --391586--

#3 ¡Pues está!

0 9
#51 --23457--

#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.

4 41
#52 --312149--

» ver comentario
#53 jmpep

#27 No es tan lento si lo implementas bien -> www.luschny.de/math/factorial/Benchmark.html. Aunque todo es relativo, claro.

0 6
#54 --174-- *

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.

3 46
#55 --312149-- *

» ver comentario
#56 ED209

#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)

0 11
#57 ED209

#32 elige: rápido o que consuma poca memoria. Engineering is about trade-offs

0 11
#58 tnt80

#55 Eso no es eficiente con comprobar hasta la raíz cuadrada de el número en cuestión sobra, no hace falta tanto

0 12
#59 orangutan

#55 En tu ejemplo,
número = 4
4%2 == 0 => ¿4 es primo?

1 18
#60 almoss

#51 Gracias. Un falso amigo, vamos.

Que conste que lo he buscado en un diccionario porque me resultaba un poco extraño.

1 18
#61 katinka_aäå

#45 No me fiaba de ti, así que he tenido que comprobarlo.

0 6
#62 SergioZgz

Como me encantan las expresiones regulares

0 9
#63 txusmah

Ya era hora, esto era un baño de sangre.

0 7
#64 ElPerroDeLosCinco

#29 Joder, me he leído el artículo entero y no lo había entendido de forma tan clara hasta ahora.

2 25
#65 ElPerroDeLosCinco

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).

1 20
#66 chavi

#65 Propongo un algoritmo que cada vez que se usa, vaya guardando los primos obtenidos para usarlos la vez siguiente...

0 8
#67 thekeeper

En meneame hay mas numeros cuñao

0 9
#68 ElPerroDeLosCinco

#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.

0 11
#69 chavi

#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.

0 8
#70 --312149--

» ver comentario
#71 --312149--

» ver comentario
#72 tnt80

#71 Yo me refería a lo que has puesto como ejemplo 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"

0 12
#73 dreierfahrer

Un desarrollador tiene un problema y decide solucionarlo con expresiones regulares....

Ahora tiene 2 problemas.

No sé quién dijo esa frase, pero q razón...

3 32
#74 code2011

- ¿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.

2 24
#75 jmav *

#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)

0 6
#76 darccio

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

0 10
#77 garnok

#7 entonces según tu es imposible calcular si un numero es primo

0 7
#78 --165145--

#77, no he dicho eso.

0 18
#79 --165145--

#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.

0 18
#80 --125581-- *

#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í.

0 10
#81 ED209

#79 correcto, y además al ahorrar la resta la fórmula que propones es un 10 % más rápida
mis dies

0 11
#82 --122466-- *

» ver comentario
#83 --165145--

#81, ¿un 10% más rápida? Lo dudo mucho, la diferencia debe de ser insignificante.

0 18
#84 --143520--

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.

0 7
#85 --143520--

#61 con una expresión regular?

1 14
#86 katinka_aäå

#85 No sabría cómo. Y eso que me he leído el artículo.

0 7