Rubi Método isPrime

Question

('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?

Answer 1

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/

Answer 2

Este é provavelmente um pouco off-topic, mas no Ruby 1.9, você pode fazer isso:

 require 'mathn'
 38749711234868463.prime?
 => false

Answer 3

require 'prime'

Prime.prime?(4)
# => false

Prime.prime?(5)
# => true

Ou:

require 'prime'

Prime.instance.prime?(4)
# => false

Prime.instance.prime?(5)
# => true

Answer 4

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:)

Answer 5

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.

Answer 6

No entanto, outro blog com uma boa explicação bastante: Famoso Perl one-liners explicada (parte III)

Answer 7

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.