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

expresiones regulares javascript

Question

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 a excepción de la expresión regular
• Tengo un conocimiento básico a avanzado básico de Regex tal como lo encuentras en las funciones integradas de PHP

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

Answer 1

Buen truco de expresiones regulares (aunque muy ineficiente) ... :)

La expresión regular define 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 representación digital simple 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 comprueba si N = 0 o N = 1, y la segunda busca un divisor K> 1, utilizando referencias retrospectivas. Obliga al motor de expresiones regulares a encontrar una subsecuencia no vacía que se puede repetir al menos dos veces para formar la secuencia. Si tal subsecuencia existe, significa que su longitud se divide en N, por lo tanto N no es primo.

Answer 2

Dijiste que entendías esta parte, pero solo para enfatizar, la Cadena generada tiene una longitud igual a la cantidad suministrada. Entonces, la cadena tiene tres caracteres si y solo si n == 3 .

.?

La primera parte de la expresión regular dice "cualquier personaje, cero o una vez". Entonces, básicamente, ¿hay cero o un carácter-- o, por lo que he mencionado anteriormente, n == 0 || n == 1 n == 0 || n == 1 . Si tenemos el partido, entonces devuelve la negación de eso. Esto se 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, dependiendo 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 utiliza 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 personaje o grupo anterior. Por lo tanto, esto no es "dos, cuatro, seis, etc.", sino "dos o tres, etc." El +? Es como +, pero intenta hacer coincidir el menor número posible de caracteres. + Normalmente intenta engullir toda la cadena si puede, lo que es malo en este caso porque impide que la parte de retro-referencia funcione.)

La siguiente parte es la retro-referencia: el mismo conjunto de caracteres (dos o más), que aparece de nuevo. Dicha referencia inversa aparece una o más veces.

Asi que. El grupo capturado corresponde a un número natural de caracteres (de 2 en adelante) capturados. Dicho grupo aparece 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 mayores o iguales a 2 que coincidan con la cadena de longitud n ... lo que significa que tiene una n compuesta. Entonces, de nuevo, devuelva la negación de la coincidencia exitosa: n NO es primo.

Si no se puede encontrar una coincidencia, entonces no se puede obtener un producto de dos números naturales mayores o iguales a 2 ... y tiene un no coinciden y un primo, por lo tanto, de nuevo 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 tienes 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 tan simple como pueda ser).

Answer 3

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

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

La forma en que funciona es que la expresión regular captura (.*) En /1 , y luego ve si hay /1+ siguiéndolo. El uso de ^ y $ asegura que una coincidencia debe ser de toda la cadena.

Entonces, de alguna manera, nos da String s , que es un "múltiplo" de String t , y la expresión regular encontrará tal t (la más larga posible, ya que /1 es codicioso).

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

• Para probar la primalidad de n , primero genere una String de longitud n (llena con el mismo char )
• La expresión regular captura una String de cierta longitud (digamos k ) en /1 , e intenta hacer coincidir /1+ con el resto de la String
  • Si hay una coincidencia, entonces n es un múltiplo apropiado de k , y por lo tanto n no es primo.
  • Si no hay coincidencia, entonces no existe tal k que divida n , y n es por lo tanto un primer

¿Cómo funciona .?|(..+?)/1+ con números primos iguales?

¡En realidad, no es así! ¡ matches String cuya longitud NO es primo!

• .? : La primera parte de la alternancia coincide con la String de longitud 0 o 1 (NO prime por definición)
• (..+?)/1+ : La segunda parte de la alternancia, una variación de la expresión regular explicada anteriormente, coincide con la String de longitud n que es "un múltiplo" de una String de longitud k >= 2 (es decir, n es una compuesto, NO un primo).
  • Tenga en cuenta que el modificador reacio ? En realidad, no es necesario para la corrección, pero puede ayudar a acelerar el proceso intentando primero k menor

Tenga en cuenta el ! operador de complemento boolean en la declaración de return : niega las matches . ¡Es cuando la expresión regular NO coincide, n es primo! Es una lógica doblemente negativa, ¡así que no es de extrañar que sea algo 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 lo mismo que el código original de Java, pero se divide en varias instrucciones con asignaciones a las 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+");

Nuevamente, dado un String de longitud n , lleno con el mismo char ,

• .{0,1} comprueba si n = 0,1 , NO primer
• (.{2,})/1+ comprueba si n es un múltiplo correcto de k >= 2 , NO es primo

¿Con la excepción del modificador reacio ? 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 usa una técnica similar; debe ser educativo:

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

Ver también

• Expresiones regulares: quién es más codicioso

Answer 4

/^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 here .