Ruby isPrime метод

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+)\1*=\1+$/.match('1' * x + '=' + '1' * y)[1].length

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

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

Answer 6

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

Answer 7

Если длина строки из единиц является составной, то строку можно разложить на несколько одинаковых подстрок, например 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-случаи.