可以判断素数的正则表达式

最近读到一个可以判断素数的正则表达式（匹配成功则不是素数）：

text

1
/^1?$|^(11+?)\1+$/
1
/^1?$|^(11+?)\1+$/

这么精炼，颇有些出乎我的意料。因为在我的印象中大多数正则表达式都十分丑陋，比如匹配邮箱的正则表达式：

text

1
(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])
1
(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])

然而，仔细阅读了一下原理后却发现它的确可以，不过需要一步预处理，即把十进制数字转换为“1的数组”：0为空字符串，1为1，2为11，3为111……
至此，就可以开始我们的匹配：

/^1?$/ 很好理解，匹配到的是空字符串（0）或 1，自然不是合数；
/^(11+?)\1+$/ 则正是该表达式的精妙所在。其利用到了正则表达式匹配时回溯的特性。让我们具体解释一下：

(11+?)匹配的是至少两个1，但是因为进行的是懒惰匹配，所以最开始匹配到的是11，并被捕获到了分组\1中。后面部分中，如果11重复了一次或者更多次，那么就是合数。这又是为什么呢？其实非常容易理解：如果数字$a$匹配成功，意味着$a$化作的“1的数组”恰好由不少于2个11组成，也就是，$\exists b>1\land b \in \mathbb N, a=2b$，这自然意味着$a$是一个合数(在这种情况下，$a$还是偶数)。
如果11匹配失败了呢？这就是本法最核心的部分了：匹配器会进行回溯，对下一个满足(11+?)的111进行\1+匹配的尝试。同理上一步，如果匹配成功，该数字大于3且含有一个因数3，自然是合数。
接下来，“匹配 - 回溯”不断进行。如果$n$是合数，会在匹配不超过$\sqrt{n}$次后成功；反之，会一直匹配到第$n$次，最后匹配失败。

可见，/^1?$|^(11+?)\1+$/的实现想法是非常朴素的：列举比$n$小的所有正整数$i$，判断$n$是否可以被$i$整除。比如：

cpp

1
2
3
4
5
6
7
//判断一个自然数是否为素数
bool isPrime(int n){
    if (n == 0 || n == 1)return false;
    if (n == 2)return true;
    for (int i = 2; i <= sqrt(n); i++)if (n % i == 0)return false;
    return true;
}
1
2
3
4
5
6
7
//判断一个自然数是否为素数
bool isPrime(int n){
    if (n == 0 || n == 1)return false;
    if (n == 2)return true;
    for (int i = 2; i <= sqrt(n); i++)if (n % i == 0)return false;
    return true;
}

但是，得到这么精炼的表达式的关键实则在于对于正则表达式匹配机制的深刻理解(懒惰匹配和回溯法的结合)，而这正是值得我们深思和学习的地方。