método Arcano esPrimo en Java

Question

Considere el siguiente método:

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

nunca he sido un gurú expresión regular, por lo que nadie puede explicar plenamente cómo este método funciona realmente? Además,, ¿es eficiente en comparación con otros métodos posibles para determinar si un entero es primo?

Answer 1

En primer lugar, tenga en cuenta que esta expresión regular se aplica a los números representados en un sistema de conteo unario, es decir

1  is 1 
11  is 2 
111  is 3 
1111 is 4 
11111 is 5 
111111 is 6 
1111111 is 7 

y así sucesivamente. Realmente, se puede usar cualquier caracter (de ahí el . s en la expresión), pero usaré "1".

En segundo lugar, tenga en cuenta que esta expresión regular coincide con compuestos (no primos) números; por lo tanto, la negación detecta la primalidad.

---

Explicación:

El primer medio de la expresión,

.? 

dice que las cadenas "" (0) y "1" (1) son partidos, es decir, no primer (por definición, though arguable.)

La segunda mitad, en inglés simple, dice s:

Haga coincidir el string más corto cuya longitud sea al menos 2, por ejemplo, "11" (2). Ahora, mira si podemos hacer coincidir toda la cadena repitiéndola. ¿Coincide "1111" (4)? ¿Coincide "111111" (6)? ¿"11111111" (8) coincide? Y así. De lo contrario, inténtelo nuevamente para la siguiente cadena más corta, "111" (3). Etc.

Ahora puede ver cómo, si la cadena original no puede ser igualada como múltiples de sus subseries, entonces, por definición, es primordial!

BTW, el operador no codicioso ? es lo que hace que el "algoritmo" comience desde el más corto y cuente hacia arriba.

---

Eficiencia:

Es interesante, pero ciertamente no es eficiente, por varios argumentos, algunos de los cuales voy a consolidarse por debajo de:

• Como notas @TeddHopp, el pozo -el enfoque conocido de tamiz-de-Eratosthenes no se molestaría en verificar múltiplos de enteros como 4, 6 y 9, habiendo sido "visitados" mientras se verificaban múltiplos de 2 y 3. Por desgracia, este enfoque de expresiones regulares comprueba exhaustivamente cada entero más pequeño.

• Como señala @PetarMinchev, podemos "cortocircuitar" el esquema de comprobación de múltiplos una vez que llegamos a la raíz cuadrada del número. Deberíamos poder hacerlo porque un factor mayor que la raíz cuadrada debe asociarse con un factor menor que la raíz cuadrada (ya que de lo contrario dos factores mayores que la raíz cuadrada producirían un producto mayor que el número), y si esto existe un factor mayor, entonces ya deberíamos haber encontrado (y por lo tanto, igualado) el factor menor.

• Como @Jesper y la nota @ Brian con concisión, desde una perspectiva no-algorítmica, considere cómo una expresión regular comenzaría por la asignación de memoria para almacenar la cadena, por ejemplo, char[9000] para 9000. Bueno, eso fue fácil, ¿no? ;)

• Como notas de @Foon, existen métodos probabilísticos que pueden ser más eficientes para números más grandes, aunque pueden no ser siempre correctos (apareciendo pseudoprimas en su lugar). Pero también hay pruebas determinísticas que son 100% precisas y mucho más eficientes que los métodos basados ​​en tamices. Wolfram's tiene un buen resumen.

Answer 2

Esta no es una manera realmente eficiente de verificar si un número es primo (verifica cada divisor).

Una manera eficiente es verificar los divisores hasta sqrt(number). Esto es si quieres estar seguro si un número es primo. De lo contrario, hay verificaciones de primalidad probabilísticas que son más rápidas, pero no 100% correctas.

Answer 3

Las características únicas de los primos y por qué este trabajo ya se ha cubierto. Así que aquí está una prueba utilizando enfoques convencionales y este enfoque:

public class Main { 

    public static void main(String[] args) { 
     long time = System.nanoTime(); 
     for (int i = 2; i < 10000; i++) { 
      isPrimeOld(i); 
     } 
     time = System.nanoTime() - time; 
     System.out.println(time + " ns (" + time/1000000 + " ms)"); 
     time = System.nanoTime(); 
     for (int i = 2; i < 10000; i++) { 
      isPrimeRegex(i); 
     } 
     time = System.nanoTime() - time; 
     System.out.println(time + " ns (" + time/1000000 + " ms)"); 
     System.out.println("Done"); 
    } 

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

    public static boolean isPrimeOld(int n) { 
     if (n == 2) 
      return true; 
     if (n < 2) 
      return false; 
     if ((n & 1) == 0) 
      return false; 
     int limit = (int) Math.round(Math.sqrt(n)); 
     for (int i = 3; i <= limit; i += 2) { 
      if (n % i == 0) 
       return false; 
     } 
     return true; 
    } 
} 

Esta prueba calcula si el número es primo hasta 9999, a partir de 2. Y aquí está su salida en un tiempo relativamente potente servidor:

8537795 ns (8 ms) 
30842526146 ns (30842 ms) 
Done 

Por lo tanto, es extremadamente ineficaz una vez que los números son lo suficientemente grandes. (Hasta 999, la expresión regular se ejecuta en aproximadamente 400 ms.) Para números pequeños, es rápido, pero es aún más rápido generar los números primos hasta 9.999 de la manera convencional que generar incluso números primos hasta 99 de la forma antigua (23 ms).