Ruby isPrime方法

Question

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

在网上，我发现这条适用于N＆gt; = 0的Ruby代码确定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

另请参阅您最辉煌的正则表达式是什么＆＃8217曾经使用过吗？（是的，我可以确认这个正则表达式最初是由阿比盖尔写的。我甚至听过她解释它是如何工作的：）

Answer 5

最大公约数（gcd）：

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

这个和is_prime都以大致相同的方式工作。它会在放弃之前尝试所有组合。

这个会尝试将偶数部分中的第一个数字拆分，并将第二个数字与这些部分中的一个或多个匹配。如果找到匹配，则返回所选部分的长度。

Answer 6

另一篇博客有一个很好的解释： Famous Perl One-Liners解释（第三部分）

Answer 7

如果1的字符串的长度是复合的，那么该字符串可以被分解成多个相同的子字符串，如111111 - ＆gt; 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个案例。