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

Eu 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+"); } 
  • Eu não conheço o Java em particular, mas entendo todos os aspectos deste trecho, exceto o próprio regex
  • Eu tenho conhecimento básico para básico-avançado do Regex como você o encontra nas funções integradas do PHP

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

Você disse que entende essa parte, mas apenas para enfatizar, a String gerada tem um comprimento igual ao número fornecido. Então a string 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, conforme mencionado acima, n == 0 || n == 1 n == 0 || n == 1 . Se tivermos a correspondência, devolva a negação disso. Isso corresponde ao fato de que zero e um não são primos.

 (..+?)\\1+ 

A segunda parte da regex é um pouco mais complicada, contando com grupos e backreferences. Um grupo é qualquer coisa entre parênteses, que será então capturado e armazenado pelo mecanismo regex para uso posterior. Uma backreference é um grupo correspondente usado posteriormente na mesma expressão regular.

O grupo captura 1 caractere, depois 1 ou mais de qualquer caractere. (O caractere + significa um ou mais, mas SOMENTE do caractere ou grupo anterior. Portanto, isso não é “dois ou quatro ou seis, etc. caracteres”, mas sim “dois ou três etc.” O +? É como +, mas ele tenta combinar o menor número de caracteres possível. + normalmente tenta devorar a cadeia inteira se puder, o que é ruim nesse caso, porque impede que a parte de referência anterior funcione.)

A próxima parte é a referência anterior: esse 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 de 2 em diante). Se houver uma correspondência, isso significa que é possível encontrar um produto de dois números maiores ou iguais a 2 que correspondam à sequência de n comprimentos … 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, então você não pode inventar um produto de dois números naturais maior ou igual a 2 … e você tem tanto um não-jogo quanto um primo, portanto, novamente o retorno da negação do resultado do jogo.

Você vê isto agora? É inacreditavelmente complicado (e computacionalmente caro!) Mas também é meio que simples ao mesmo tempo, uma vez que você o obtém. 🙂

Eu posso elaborar se você tiver mais perguntas, por exemplo, como funciona a análise de expressões regulares. Mas estou tentando manter essa resposta simples por enquanto (ou tão simples quanto pode ser).

Eu explicarei a parte de regex fora do teste de primalidade: o seguinte regex, dado um String s que consiste em repetir String t , encontra t .

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

A maneira como isso funciona é que o regex captura (.*) Em \1 e, em seguida, vê se há \1+ seguindo-o. Usando o ^ e $ garante que uma correspondência deve ser da cadeia inteira.

Então, de certa forma, nós recebemos String s , que é um “múltiplo” de String t , e o regex vai achar tal t (o mais longo possível, desde que \1 seja ganancioso).

Uma vez que você entenda porque este regex funciona, então (ignorando a primeira alternativa no regex do OP por enquanto) explicar como é usado para teste de primalidade é simples.

  • Para testar a primality de n , primeiro gere uma String de comprimento n (preenchida com o mesmo char )
  • A regex captura uma String de comprimento (digamos k ) em \1 e tenta corresponder a \1+ ao resto da String
    • Se houver uma correspondência, então n é um múltiplo adequado de k e, portanto, n não é primo.
    • Se não houver correspondência, então não existe tal k que divida n , e n é, portanto, um primo

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

Na verdade, isso não acontece! Corresponde a String cujo comprimento NÃO é primo!

  • .? : A primeira parte da alternância corresponde à String de comprimento 0 ou 1 (NÃO primo por definição)
  • (..+?)\1+ : A segunda parte da alternância, uma variação da regex explicada acima, corresponde a String de comprimento n que é “um múltiplo” de uma String de comprimento k >= 2 (ou seja, n é um composto, NÃO é um primo).
    • Note que o modificador relutante ? na verdade não é necessário para correção, mas pode ajudar a acelerar o processo, tentando menor k primeiro

Observe o ! operador de complemento boolean na declaração de return : nega os matches . É quando o regex não combina, n é primo! É uma lógica negativa dupla, então não admira que seja meio confuso !!


Simplificação

Aqui está uma simples reescrita 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 atribuições a variables ​​locais para facilitar a compreensão da lógica.

Nós também podemos simplificar o regex, usando a repetição finita, como segue:

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

Novamente, dada uma String de comprimento n , preenchida com o mesmo char ,

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

Com exceção do modificador relutante ? em \1 (omitido para maior clareza), o regex acima é idêntico ao original.


Regex mais divertido

O seguinte regex 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

  • Expressões regulares: quem é mais ganancioso

Bom regex truque (embora muito ineficiente) … 🙂

O regex define não-primes da seguinte maneira:

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

Em vez de passar a representação digital simples de N para o motor regex, ele é alimentado com uma sequência de comprimento N, composta de um caractere repetitivo. A primeira parte da disjunit verifica N = 0 ou N = 1, e a segunda procura um divisor K> 1, usando referências anteriores. Ele força o mecanismo de regex a encontrar alguma subseqüência não vazia que pode ser repetida pelo menos duas vezes para formar a sequência. Se tal subsequência existe, isso significa que seu comprimento divide N, portanto N não é primo.

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

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

Explicação aqui .