Abigail的质数识别正则式

Perl代码：

sub is_prime {
    my ($n) = @_;
    return ( 1 x $n ) !~ m/ \A ( ?: 1? | (11+?) (?> \1+ ) ) \Z /xms;
}

解析：

非质数包括

• 0
• 1
• >=4的、能被>1的数整除的数

\A 表示 1… 串的开始

\Z 表示 1… 串的结束

?: 1?  匹配 0 和 1

11+？匹配 >1的数的 11… 串，也就是说第一部分至少是2

(?> \1 + ) 表示 当前的 1… 串可以被>1的数整除，也就是说，至少是前面匹配的第一部分的2倍

(11+?) (?> \1+) 至少是 2x2=4

目前还没想好的问题：

11+？应该是从 11，111，1111，… 这样递增检测到最后才确定$n是质数的，那么，

假如先确定了$n不能被2整除，还会再去检测$n能否被4整除。

这种情况应该是重复检测了。。。