¿Cómo encuentra este regex primos?

primes

Question

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

Esta página afirma que esta expresión regular descubre números no primos (y por contraejemplo: primos):

/^1?$|^(11+?)/1+$/

¿Cómo encuentra esto primos?

Answer 1

Creo que el artículo lo explica bastante bien, pero voy a intentarlo también.

La entrada está en forma unary . 1 es 1 , 2 es 11 , 3 es 111 , etc. Cero es una cadena vacía.

La primera parte de la expresión regular coincide con 0 y 1 como no primo. El segundo es donde entra la magia.

(11+?) Comienza encontrando divisores. Comienza definiéndose como 11 o 2. /1 es una variable que se refiere a la coincidencia previamente capturada, por lo que /1+ determina si el número es divisible por ese divisor. ( 111111 comienza asignando la variable a 11 , y luego determina que el 1111 restante se repite 11 , por lo que 6 es divisible por 2.)

Si el número no es divisible por dos, el motor regex incrementa el divisor. (11+?) convierte en 111 , y lo intentamos de nuevo. Si en algún momento la expresión regular coincide, el número tiene un divisor que no produce ningún resto, por lo que el número no puede ser primo.

Answer 2

Me tomó un minuto darme cuenta de que esto es para números en base-1 (¿unario?)

Varias personas en esta discusión de ycombinator explican esto bastante bien. En realidad, esas explicaciones son más sucintas de lo que creo que puedo obtener, así que lo dejo al enlace.