Pergunta
('1' * N) !~ /^1?$|^(11+?)\1+$/
Na net, encontrei este pedaço de código Ruby que funciona para N> = 0 que determina se ou não N é primo. Do que eu posso dizer, parece que jogo com regex, mas não tenho idéia de como ele funciona. Alguém poderia me dizer como ele funciona?
Solução
Você pode encontrar uma longa explicação deste código aqui: http: // www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
Outras dicas
Este é provavelmente um pouco off-topic, mas no Ruby 1.9, você pode fazer isso:
require 'mathn'
38749711234868463.prime?
=> false
require 'prime'
Prime.prime?(4)
# => false
Prime.prime?(5)
# => true
Ou:
require 'prime'
Prime.instance.prime?(4)
# => false
Prime.instance.prime?(5)
# => true
Veja também Qual é o regex mais brilhante você tem ? já usou (. e sim, posso confirmar que este regexp foi originalmente escrito por Abigail Eu mesmo ouvi-la explicar como funciona:)
máximo divisor comum (mdc):
/^(1+)\1*=\1+$/.match('1' * x + '=' + '1' * y)[1].length
Tanto este como os is_prime um funciona em cerca da mesma maneira. Ele tenta todas as combinações antes de desistir.
Este vai tentar dividir o primeiro número em partes mesmo, e combinar o segundo número com um ou mais dessas partes. Se ele encontrar uma correspondência ele retorna o comprimento da parte selecionada.
No entanto, outro blog com uma boa explicação bastante: Famoso Perl one-liners explicada (parte III)
Se o comprimento de uma cadeia de 1 de compósito é, em seguida, a cadeia pode ser decomposta em várias subsequências idênticos, como 111111 -> 11 11 11
Por exemplo, 1111111111, tem 10 um de, e que corresponde ao (11) {5} ou (11111) {2}, em que {2} meios repetido 2 vezes. 111111111, tem 9 1 do, e ele corresponde (111) {3}.
Ao generalizar a contagem de 1 e o número na {}, o regexp é
/(1{2,}){2,}/
.
No entanto, 1 {2} também pode ser escrita como 11+, e (...) {2} pode ser reescrita como (...) \ 1+, com referências anteriores.
A parte ^1?$
nos primeiros cheques alternância para 0 e 1-casos.