Domanda
('1' * N) !~ /^1?$|^(11+?)\1+$/
In rete, ho trovato questo pezzo di codice Ruby che funziona per N > = 0 che determina se N è o meno un numero primo. Da quello che posso dire, sembra giocare con regex ma non ho idea di come funzioni. Qualcuno potrebbe dirmi come funziona?
Soluzione
Puoi trovare una lunga spiegazione di questo codice qui: http: // www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
Altri suggerimenti
Questo è probabilmente piuttosto fuori tema, ma in Ruby 1.9, puoi farlo:
require 'mathn'
38749711234868463.prime?
=> false
require 'prime'
Prime.prime?(4)
# => false
Prime.prime?(5)
# => true
o
require 'prime'
Prime.instance.prime?(4)
# => false
Prime.instance.prime?(5)
# => true
Vedi anche Qual è la regex più brillante che hai mai usato? (e sì, posso confermare che questa regexp è stata originariamente scritta da Abigail. L'ho persino sentita spiegare come funziona :)
Greatest Common Divisor (gcd):
/^(1+)\1*=\1+$/.match('1' * x + '=' + '1' * y)[1].length
Sia questo che is_prime funzionano allo stesso modo. Prova tutte le combinazioni prima di arrendersi.
Questo tenterà di dividere il primo numero in parti pari e abbinare il secondo numero con una o più di quelle parti. Se trova una corrispondenza, restituisce la lunghezza della parte selezionata.
Ancora un altro blog con una spiegazione abbastanza buona: Famoso Perl One-Liners Explained (parte III)
Se la lunghezza di una stringa di 1 è composita, la stringa può essere scomposta in più sottostringhe identiche, come 111111 - > 11 11 11
Ad esempio, 1111111111, ha 10 1 e corrisponde a (11) {5} o (11111) {2}, dove {2} significa ripetuto 2 volte. 111111111, ha 9 1 e corrisponde a (111) {3}.
Generalizzando il conteggio di 1 e il numero in {}, regexp è
/ (1 {2,}) {2,} /
.
Tuttavia, 1 {2,} può anche essere scritto come 11+ e (...) {2,} può essere riscritto come (...) \ 1+, con riferimenti indietro.
La parte ^ 1? $
nella prima alternanza verifica i casi 0 e 1.