Ruby isPrime Method

Question

('1' * N) !~ /^1?$|^(11+?)\1+$/

В сети я нашел этот фрагмент кода Ruby, который работает для N> = 0, который определяет, является ли N простым. Из того, что я могу сказать, это похоже на игру с регулярным выражением, но я понятия не имею, как это работает. Может кто-нибудь сказать мне, как это работает?

Answer 1

Вы можете найти подробное объяснение этого кода здесь: http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

Answer 2

Это, скорее всего, не по теме, но в Ruby 1.9 вы можете сделать это:

 require 'mathn'
 38749711234868463.prime?
 => false

Answer 3

require 'prime'

Prime.prime?(4)
# => false

Prime.prime?(5)
# => true

Или:

require 'prime'

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

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

Answer 4

См. Также Какое самое блестящее регулярное выражение, которое вы когда-либо использовали? (и да, я могу подтвердить, что это регулярное выражение было изначально написано Абигейл. Я даже слышал, как она объясняет, как это работает: )

Answer 5

Если длина строки из 1 является составной, то строку можно разложить на несколько одинаковых подстрок, например 111111 -> 11 11 11

Например, 1111111111 имеет 10 единиц и соответствует (11) {5} или (11111) {2}, где {2} означает повторение 2 раза. 111111111, имеет 9 единиц и соответствует (111) {3}.

Обобщая количество единиц и число в {}, регулярное выражение равно /(1{2,}){2,}/. Однако 1 {2,} также можно записать как 11+, а (...) {2,} можно переписать как (...) \ 1+ с обратными ссылками.

Часть ^1?$ в первом чередовании проверяет 0 и 1 случаи.

Answer 6

Еще один блог с довольно хорошим объяснением: Объяснения знаменитых Perl One-Liners (часть III)

Answer 7

Величайший общий делитель (gcd):

/^(1+)\1*=\1+$/.match('1' * x + '=' + '1' * y)[1].length

И this, и is_prime работают примерно одинаково. Он пробует все комбинации, прежде чем сдаться.

Этот попытается разделить первое число на четные части и сопоставить второе число с одной или несколькими из этих частей. Если он находит совпадение, он возвращает длину выбранной детали.