('1' * N) !~ /^1?$|^(11+?)\1+$/
В сети я нашел этот кусок кода Ruby, который работает для N >= 0, который определяет, является ли N простым. Из того, что я могу сказать, похоже на игру с регулярным выражением, но я не знаю, как это работает. Может ли кто-нибудь сказать мне, как это работает?
Здесь вы можете найти подробное объяснение этого кода: http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
Это, вероятно, довольно не по теме, но в Ruby 1.9 вы можете сделать это:
require 'mathn'
38749711234868463.prime?
=> false
require 'prime'
Prime.prime?(4)
# => false
Prime.prime?(5)
# => true
Или:
require 'prime'
Prime.instance.prime?(4)
# => false
Prime.instance.prime?(5)
# => true
См. также Что такое наиболее яркое регулярное выражение, которое вы когда-либо использовали? (и да, я могу подтвердить, что это регулярное выражение было первоначально написано Abigail.Я даже слышал она объясняет, как это работает:)
Самый большой общий делитель (gcd):
/^(1+)\1*=\1+$/.match('1' * x + '=' + '1' * y)[1].length
И это, и is_prime работают примерно одинаково. Он пытается выполнить все комбинации перед тем, как отказаться.
Это попытается разбить первое число на четные части и сопоставить второе число с одной или несколькими из этих частей. Если он находит совпадение, он возвращает длину выбранной части.
Еще один блог с довольно хорошим объяснением: Известный поясник с одним слоем (часть III)
Если длина строки из 1 является составной, то строка может быть разложена на несколько одинаковых подстрок, например 111111 → 11 11 11
Например, 1111111111 имеет 10 1, и он соответствует (11) {5} или (11111) {2}, где {2} означает повторение 2 раза. 111111111, имеет 9 1, и он соответствует (111) {3}.
Обобщая число 1 и число в {}, регулярное выражение
/(1{2,}){2,}/.
Однако 1 {2,} также может быть записано как 11+, и (...) {2,} можно переписать в виде (...)\1+ с обратными ссылками.
Часть ^1?$ в первом чередовании проверяет 0 и 1 случай.