¿Cómo determinar si un número es primo con expresiones regulares?

128

Encontré el siguiente ejemplo de código para Java en RosettaCode :

public static boolean prime(int n) {
  return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
  • No conozco Java en particular, pero entiendo todos los aspectos de este fragmento, excepto la expresión regular en sí.
  • Tengo conocimiento básico a básico-avanzado de Regex tal como lo encuentra en las funciones integradas de PHP

¿Cómo .?|(..+?)\\1+coincide los números primos?

kitlite
fuente
9
@Amir Rachum: !new String(new char[n]).matches(".?|(..+?)\\1+")es equivalente a !((new String(new char[n])).matches(".?|(..+?)\\1+")).
Gumbo
14
Esto no solo es computacionalmente costoso, sino que también es potencialmente devastador para la memoria. Si alguien opta por utilizar este enfoque, que desaconsejaría ya que el algoritmo para encontrar números primos es tan simple (por qué en el mundo lo complica y lo hace tan derrochador), se debe realizar una verificación antes del "nuevo carácter [n ] "para garantizar que esté por debajo de un umbral razonable. Por ejemplo, llame a "prime (Integer.MAX_VALUE)" y luego presente un error cuando arroje OutOfMemoryError.
nicerobot
28
@nicerobot: ¿Aligerar?
Cam
66
@nicerobot: en realidad, lo retiro. Originalmente pensé que la naturaleza académica de esta pregunta implicaba su uso solo con fines de aprendizaje, y que estabas siendo un idiota desagradable. Sin embargo, pensándolo bien, ese no es el caso; nunca se menciona ni se da a entender en la pregunta que la expresión regular es solo para fines de aprendizaje. De hecho, mi primera impresión es que es muy simple en lo que respecta a los fragmentos de código, por lo que un principiante podría suponer que podría usarse en la práctica. +1.
Cam
77
@incrediman no te preocupes. Puedo ver cómo piensas eso. Era solo mi intención advertir sobre las consecuencias de usar esto, no desanimar a aprender cómo funciona. Un simple "Por favor, no despliegue esto". antes del resto de mi comentario podría haber hecho que parezca menos condescendiente desde su perspectiva inicial.
nicerobot

Respuestas:

120

Dijiste que entiendes esta parte, pero solo para enfatizar, la cadena generada tiene una longitud igual al número proporcionado. Entonces la cadena tiene tres caracteres si y solo si n == 3.

.?

La primera parte de la expresión regular dice: "cualquier carácter, cero o una vez". Así que, básicamente, no es cero o uno o character--, por lo que he mencionado anteriormente, n == 0 || n == 1. Si tenemos el partido, entonces devuelve la negación de eso. Esto corresponde con el hecho de que cero y uno NO son primos.

(..+?)\\1+

La segunda parte de la expresión regular es un poco más complicada, ya que depende de grupos y referencias. Un grupo es cualquier cosa entre paréntesis, que luego será capturado y almacenado por el motor de expresiones regulares para su uso posterior. Una referencia inversa es un grupo coincidente que se usa más adelante en la misma expresión regular.

El grupo captura 1 personaje, luego 1 o más de cualquier personaje. (El carácter + significa uno o más, pero SOLO del carácter o grupo anterior. Por lo tanto, no se trata de "dos o cuatro o seis caracteres, etc.", sino más bien "dos o tres, etc." El +? Es como +, pero intenta hacer coincidir la menor cantidad posible de caracteres. + normalmente intenta engullir toda la cadena si puede, lo cual es malo en este caso porque evita que la parte de referencia inversa funcione).

La siguiente parte es la referencia: ese mismo conjunto de caracteres (dos o más), que aparecen nuevamente. Dicha referencia aparece una o más veces.

Entonces. El grupo capturado corresponde a un número natural de caracteres (de 2 en adelante) capturados. Dicho grupo aparece entonces un número natural de veces (también de 2 en adelante). Si hay una coincidencia, esto implica que es posible encontrar un producto de dos números mayor o igual a 2 que coincida con la cadena de longitud n ... lo que significa que tiene una n compuesta. Entonces, nuevamente, devuelva la negación de la coincidencia exitosa: n NO es primo.

Si no se puede encontrar una coincidencia, entonces no puede obtener un producto de dos números naturales mayores o iguales a 2 ... y tiene tanto una no coincidencia como un primo, por lo tanto, nuevamente el retorno de la negación del resultado del partido.

lo ves ahora? Es increíblemente complicado (¡y computacionalmente costoso!) Pero también es algo simple al mismo tiempo, una vez que lo obtienes. :-)

Puedo elaborar si tiene más preguntas, como sobre cómo funciona realmente el análisis de expresiones regulares. Pero estoy tratando de mantener esta respuesta simple por ahora (o lo más simple posible).

Azul platino
fuente
10
Probé esta lógica con JS en la consola de desarrollo de Chrome. en la página web y solo pasé 5 para verificar. ¡La página se estrelló!
Amogh Talpallikar
El comentario a continuación da una mejor explicación. ¡Léalo antes de continuar!
Ivan Davidov
"Mejor" es subjetivo. Diría que aborda el problema desde un ángulo diferente y es un complemento maravilloso para esta respuesta. :-)
Platinum Azure
1
De hecho, escribí una publicación de blog explicando esto con más detalle: Desmitificando la expresión regular que verifica si un número es primo .
Illya Gerasymchuk
73

Explicaré la parte de la expresión regular fuera de la prueba de primalidad: la siguiente expresión regular, dada una String sque consiste en repetir String t, encuentra t.

    System.out.println(
        "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1")
    ); // prints "Mamamia"

La forma en que funciona es que las capturas de expresiones regulares (.*)en \1, y luego ve si hay \1+tras ella. El uso de ^y $asegura que una coincidencia debe ser de toda la cadena.

Entonces, en cierto modo, se nos da String s, que es un "múltiplo" de String t, y la expresión regular encontrará tal t(el más largo posible, ya que \1es codicioso).

Una vez que comprenda por qué funciona esta expresión regular, entonces (ignorando la primera alternativa en la expresión regular de OP por ahora) explicando cómo se usa para la prueba de primalidad es simple.

  • Para probar la primalidad de n, primero genere un Stringde longitud n(rellenado con el mismo char)
  • La expresión regular captura un Stringpoco de longitud (digamos k) \1e intenta hacer coincidir \1+con el resto de laString
    • Si hay una coincidencia, entonces nes un múltiplo adecuado de ky, por nlo tanto, no es primo.
    • Si no hay coincidencia, entonces no kexiste tal cosa que se divida ny, npor lo tanto , sea ​​primordial

¿Cómo .?|(..+?)\1+coincide los números primos?

En realidad, no lo hace! ¡ Coincide con la String longitud que NO es primo!

  • .?: La primera parte de las coincidencias Stringde alternancia de longitud 0o 1(NO primo por definición)
  • (..+?)\1+: La segunda parte de la alternancia, una variación de la expresión regular explicada anteriormente, coincide con la Stringlongitud nque es "un múltiplo" de una Stringlongitud k >= 2( nes decir, es un compuesto, NO un primo).
    • Tenga en cuenta que el modificador reacio ?no es realmente necesario para la corrección, pero puede ayudar a acelerar el proceso al intentar kprimero más pequeño

Tenga en cuenta el ! booleanoperador de complemento en la returndeclaración: niega el matches. Es cuando la expresión regular NO coincide, ¡ nes primordial! Es una lógica doblemente negativa, ¡así que no es de extrañar que sea un poco confuso!


Simplificación

Aquí hay una reescritura simple del código para hacerlo más legible:

public static boolean isPrime(int n) {
    String lengthN = new String(new char[n]);
    boolean isNotPrimeN = lengthN.matches(".?|(..+?)\\1+");
    return !isNotPrimeN;
}

Lo anterior es esencialmente el mismo que el código Java original, pero se divide en varias declaraciones con asignaciones a variables locales para facilitar la comprensión de la lógica.

También podemos simplificar la expresión regular, utilizando la repetición finita, de la siguiente manera:

boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+");

De nuevo, dado un Stringlargo n, lleno de lo mismo char,

  • .{0,1}comprueba si n = 0,1, NO cebar
  • (.{2,})\1+comprueba si nes un múltiplo adecuado de k >= 2, NO cebar

Con la excepción del modificador reacios ?en \1(omitido para mayor claridad), la expresión regular anterior es idéntica a la original.


Más diversión regex

La siguiente expresión regular utiliza una técnica similar; debería ser educativo:

System.out.println(
    "OhMyGod=MyMyMyOhGodOhGodOhGod"
        .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!")
); // prints "Oh! My! God!"

Ver también

poligenelubricantes
fuente
66
+1: Creo que tu enfoque es probablemente mejor que el mío. No tengo idea de por qué obtuve tantos votos a favor o la marca de verificación ... creo que te lo mereces más. :-( Lo siento
Platinum Azure
@Platinum: ¡Guau, nunca pensé que irías a decir eso públicamente! Gracias por el apoyo. Quizás tenga [Populist]algún día de esto.
Polygenelubricants
2
Bueno, es solo la verdad (como lo percibo) ... no es un gran problema en realidad. No estoy aquí para el representante (aunque siempre es un bono y una sorpresa agradable) ... Estoy aquí para tratar de responder preguntas cuando puedo. Por lo tanto, no debería sorprender que pueda admitir cuando alguien lo ha hecho mejor que yo en una pregunta en particular.
Platinum Azure
25

Buen truco regex (aunque muy ineficiente) ... :)

La expresión regular define los no primos de la siguiente manera:

N no es primo si y solo si N <= 1 O N es divisible por alguna K> 1.

En lugar de pasar la simple representación digital de N al motor de expresiones regulares, se alimenta con una secuencia de longitud N, compuesta de un carácter repetitivo. La primera parte de la disyunción verifica N = 0 o N = 1, y la segunda busca un divisor K> 1, utilizando referencias posteriores. Obliga al motor regex a encontrar alguna subsecuencia no vacía que se puede repetir al menos dos veces para formar la secuencia. Si existe tal subsecuencia, significa que su longitud divide N, por lo tanto, N no es primo.

Eyal Schneider
fuente
2
Por extraño que parezca, incluso después de leer repetidamente las otras explicaciones más largas y más técnicas, encontré que esta explicación fue la que hizo que 'haga clic' en mi cabeza.
Eight-Bit Guru
2
/^1?$|^(11+?)\1+$/

Aplicar a los números después de la conversión a la base 1 (1 = 1, 2 = 11, 3 = 111, ...). Los no primos coincidirán con esto. Si no coincide, es primo.

Explicación aquí .

Dinah
fuente