perl : Abigail的质数识别正则式

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整除。

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