Como determinar se um número é primo com regex?

128

Encontrei o seguinte exemplo de código para Java no RosettaCode :

public static boolean prime(int n) {
  return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
  • Não conheço Java em particular, mas entendo todos os aspectos desse snippet, exceto o próprio regex
  • Eu tenho conhecimentos básicos e básicos avançados do Regex, como você o encontra nas funções PHP integradas

Como .?|(..+?)\\1+corresponde aos números primos?

kitlite
fonte
9
@Amir Rachum: !new String(new char[n]).matches(".?|(..+?)\\1+")é equivalente a !((new String(new char[n])).matches(".?|(..+?)\\1+")).
Gumbo
14
Isso não é apenas computacionalmente caro, mas também potencialmente devastadoramente caro para a memória. Se alguém optar por usar essa abordagem, contra a qual eu desaconselho, já que o algoritmo para encontrar números primos é tão simples (por que o mundo o complica e o torna tão inútil), uma verificação deve ser realizada antes do "novo caractere [n ] "para garantir que esteja abaixo de um limite razoável. Por exemplo, chame "prime (Integer.MAX_VALUE)" e, em seguida, registre um erro ao lançar o OutOfMemoryError.
Nicerobot
28
@nicerobot: Clareou?
Cam
6
@ nicerobot: na verdade, eu retiro isso. Originalmente, imaginei que a natureza acadêmica dessa questão implicava seu uso apenas para fins de aprendizado e que você estava sendo um idiota desagradável. No entanto, pensando bem, esse não é o caso; nunca é mencionado ou mesmo implícito na pergunta de que o regex é apenas para fins de aprendizado. De fato, minha primeira impressão é que é muito simples, no que diz respeito aos trechos de código, para que um iniciante possa realmente assumir que poderia ser usado na prática. +1.
Cam
7
@incrediman não se preocupe. Eu posso ver como você pode pensar isso. Era apenas minha intenção alertar sobre as conseqüências do uso disso, não desencorajar o aprendizado de como funciona. Um simples "Por favor, não implante isso". antes do resto do meu comentário, poderia ter soado menos condescendente da sua perspectiva inicial.
Nicerobot

Respostas:

120

Você disse que entende esta parte, mas apenas para enfatizar, a String gerada tem um comprimento igual ao número fornecido. Portanto, a cadeia tem três caracteres se e somente se n == 3.

.?

A primeira parte do regex diz: "qualquer caractere, zero ou uma vez". Então, basicamente, existe zero ou um caractere - ou, pelo que mencionei acima n == 0 || n == 1,. Se tivermos a correspondência, retorne a negação disso. Isso corresponde ao fato de que zero e um NÃO são primos.

(..+?)\\1+

A segunda parte do regex é um pouco mais complicada, contando com grupos e referências anteriores. Um grupo é qualquer coisa entre parênteses, que será capturado e armazenado pelo mecanismo regex para uso posterior. Uma referência anterior é um grupo correspondido que é usado posteriormente no mesmo regex.

O grupo captura 1 caractere e depois 1 ou mais de qualquer caractere. (O caractere + significa um ou mais, mas SOMENTE do caractere ou grupo anterior. Portanto, não são "dois, quatro, seis, etc. caracteres", mas sim "dois ou três, etc." O +? É como +, mas ele tenta corresponder o mínimo de caracteres possível. + normalmente tenta devorar toda a cadeia, se puder, o que é ruim neste caso, porque impede que a parte de referência anterior funcione.)

A próxima parte é a referência anterior: o mesmo conjunto de caracteres (dois ou mais), aparecendo novamente. A referida referência anterior aparece uma ou mais vezes.

Assim. O grupo capturado corresponde a um número natural de caracteres (de 2 em diante) capturados. O referido grupo aparece então um número natural de vezes (também a partir de 2). Se houver uma correspondência, isso implica que é possível encontrar um produto com dois números maiores ou iguais a 2 que correspondam à cadeia de comprimento n ... o que significa que você tem um n composto. Então, novamente, retorne a negação da correspondência bem-sucedida: n NÃO é primo.

Se nenhuma correspondência puder ser encontrada, você não poderá criar um produto com dois números naturais maior ou igual a 2 ... e você terá uma correspondência e uma primo, portanto, novamente o retorno da negação do resultado da partida.

Você vê isto agora? É incrivelmente complicado (e computacionalmente caro!), Mas também é meio simples ao mesmo tempo, quando você o entende. :-)

Posso elaborar se você tiver mais perguntas, como sobre como a análise de expressões regulares realmente funciona. Mas estou tentando manter essa resposta simples por enquanto (ou o mais simples possível).

Platinum Azure
fonte
10
Eu tentei essa lógica com JS no console do desenvolvedor do chrome. na página da web. e apenas passou 5 para verificar. A página falhou!
Amogh Talpallikar
O comentário abaixo fornece uma explicação melhor. Por favor, leia-o antes de prosseguir!
Ivan Davidov 26/09
"Melhor" é subjetivo - eu diria que aborda o problema de um ângulo diferente e é um complemento maravilhoso para essa resposta. :-)
Platinum Azure
1
Na verdade, escrevi um post no blog explicando isso com mais detalhes: Desmistificando a expressão regular que verifica se um número é primo .
Illya Gerasymchuk 8/09/16
73

Explicarei a parte da regex fora do teste de primalidade: a seguinte regex, dada uma String sque consiste em repetir String t, encontra t.

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

O modo como funciona é que a captura de regex (.*)para \1, em seguida, vê se há \1+que se lhe segue. O uso de ^e $garante que uma correspondência deve ser de toda a cadeia.

Então, de certa forma, nos é dado String s, que é um "múltiplo" de String t, e o regex o encontrará t(o mais longo possível, pois \1é ganancioso).

Depois de entender por que esse regex funciona, então (ignorando a primeira alternativa no regex do OP por enquanto) é simples explicar como é usado para o teste de primalidade.

  • Para testar a primalidade de n, primeiro gere um Stringcomprimento n(preenchido com o mesmo char)
  • O regex captura um Stringpouco de comprimento (digamosk ) \1e tenta corresponder \1+ao resto doString
    • Se houver uma correspondência, então n é um múltiplo adequado de ke, portanto, nnão é primo.
    • Se não houver correspondência, não kexiste uma que se divida ne, nportanto , é a principal

Como .?|(..+?)\1+corresponde aos números primos?

Na verdade, não! ele corresponde String cujo comprimento não é primo!

  • .? : A primeira parte da alternância corresponde String ao comprimento 0ou 1(NÃO é definido por definição)
  • (..+?)\1+: A segunda parte da alternância, uma variação do regex explicado acima, corresponde a um Stringcomprimento n"múltiplo" de um Stringcomprimento k >= 2(isto né, um composto, NÃO um primo).
    • Observe que o modificador relutante ?não é realmente necessário para a correção, mas pode ajudar a acelerar o processo tentando kprimeiro menor

Observe o ! booleanoperador complemento na returndeclaração: ele nega o matches. É quando o regex NÃO corresponde, né primo! É uma lógica dupla-negativa, então não admira que seja meio confuso !!


Simplificação

Aqui está uma reescrita simples do código para torná-lo mais legível:

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

O acima é essencialmente o mesmo que o código Java original, mas dividido em várias instruções com designações para variáveis ​​locais para facilitar a compreensão da lógica.

Também podemos simplificar a regex, usando repetição finita, da seguinte maneira:

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

Novamente, dado um Stringcomprimento n, preenchido com o mesmo char,

  • .{0,1}verifica se n = 0,1, NÃO prime
  • (.{2,})\1+verifica se né um múltiplo adequado de k >= 2, NÃO é primo

Com a excepção do modificador relutantes ?em \1(omitidas para maior clareza), a expressão regular acima é idêntico ao original.


Regex mais divertido

O regex a seguir usa técnica semelhante; deve ser educacional:

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

Veja também

poligenelubricants
fonte
6
+1: acho que sua abordagem provavelmente é melhor que a minha. Não faço ideia por que recebi tantos votos positivos ou a marca de seleção ... você merece mais, eu acho. :-( Desculpe
Platinum Azure
@Platinum: Uau, eu nunca pensei que você sairia por aí dizendo isso publicamente! Obrigado pelo apoio. Talvez eu tenha um [Populist]dia com isso.
polygenelubricants
2
Bem, é apenas a verdade (como eu a percebo) ... não é realmente um grande negócio. Não estou aqui para rep (embora seja sempre um bônus e uma agradável surpresa) ... Estou aqui para tentar responder a perguntas sempre que posso. Portanto, não é de surpreender que eu possa admitir quando alguém fez isso melhor do que eu em uma pergunta específica.
Platinum Azure
25

Bom truque regex (embora muito ineficiente) ... :)

O regex define não primos da seguinte maneira:

N não é primo se e somente se N <= 1 OR N é divisível por alguns K> 1.

Em vez de passar a representação digital simples de N para o mecanismo de expressão regular, ela é alimentada com uma sequência de comprimento N, composta por um caractere repetido. A primeira parte da disjunção verifica N = 0 ou N = 1, e a segunda procura um divisor K> 1, usando referências anteriores. Força o mecanismo regex a encontrar uma sub-sequência não vazia que pode ser repetida pelo menos duas vezes para formar a sequência. Se existe uma subsequência, significa que seu comprimento divide N, portanto N não é primo.

Eyal Schneider
fonte
2
Por incrível que pareça, mesmo depois de ler repetidamente as outras explicações mais longas e mais técnicas, achei essa explicação a que a fez 'clicar' na minha cabeça.
Oito Bit Guru
2
/^1?$|^(11+?)\1+$/

Aplique aos números após a conversão na base 1 (1 = 1, 2 = 11, 3 = 111, ...). Não primos corresponderão a isso. Se não corresponder, é primo.

Explicação aqui .

Dinah
fonte