¿Cómo funciona esta expresión regular?

Question

De this article,

/^1?$|^(11+?)\1+$/ comprueba si un número (su valor en unario) es principal o no.

Al usar esto, perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;' devuelve una lista de números primos.

No tengo suficiente experiencia con Perl, pero lo que entiendo es que la expresión regular será true para un número que no sea primer. Entonces, si imprimimos todos los números que no producen un true con esta expresión, tenemos una lista de números primos. Eso es lo que intenta hacer la consulta perl.

Sobre la parte de expresiones regulares,

^1?$ parte es para contar como 1 no se ceba

^(11+?)\1+$ es para hacer coincidir los números no primos a partir de 4.

---

Lo que no hago entiendo por qué es el ? en la expresión regular necesaria en absoluto. Según yo /^1$|^(11+)\1+$/ debe estar muy bien y en realidad

perl -l -e '(1 x $_) !~ /^1$|^(11+)\1+$/ && print while ++$_;' me da el mismo conjunto de números primos.

¿Hay alguna falla en mi comprensión de la expresión regular? ¿Por qué se necesitan ? s?

¿No se supone que ? coincide con cero o una aparición de la expresión que lo precede?

Answer 1

La primera ? es para hacer coincidir la cadena vacía (es decir, 0) como no principal. Si no te importa si la expresión regular coincide con 0, entonces no es necesario.

El segundo ? es solo por eficiencia. + es normalmente "codicioso", lo que significa que coincide con tantos caracteres como están disponibles, y luego retrocede si el resto de la expresión regular no coincide. El +? lo hace no codicioso, por lo que solo coincide con 1 carácter, y luego intenta hacer coincidir más si el resto de la expresión regular no coincide. (Consulte the Quantifiers section of perlre para obtener más información sobre concordancia entre codiciosos y no codiciosos).)

En este regexp particular, la (11+?) significa que las pruebas de divisibilidad por 2 ('11'), a continuación, 3 ('111'), a continuación, 4, etc. Si utilizó (11+), sería probar divisibilidad por N (el número en sí), luego N-1, luego N-2, etc. Dado que un divisor no debe ser mayor que N/2, sin el ? perdería el tiempo probando una gran cantidad de divisores "potenciales" que no pueden funcionar. Todavía igualaría los números no primos, solo que más lentamente. (Además, $1 sería el divisor más grande en lugar del más pequeño).

Answer 2

La primera ? hará que "" (la cadena vacía, cero unario) no sea un número primo. Cero se define como no primo.

El segundo es diferente; detiene la expresión regular de la coincidencia codiciosa. Debe mejorar el rendimiento de la coincidencia en gran medida, ya que la primera parte de esa sección ((11+)) no consumirá casi toda la cadena antes de tener que retroceder. Si omite el signo de interrogación, efectivamente se está probando si el n impar es divisible por n-1 y, por lo tanto, uno abajo; si lo incluye, está probando la divisibilidad por dos, y así sucesivamente. Obviamente, los números tienden a ser divisibles por factores más pequeños con más frecuencia, por lo que su coincidencia será más rápida.