可以判断素数的正则表达式!
敲有意思
最近在阮一峰老师的订阅上看到一篇文章,讲了一个特别有意思的验证素数的正则表达式。
^1?$|^(11+?)\1+$
用法
刚看到这个正则表达式的时候真的令人惊讶:什么,就这两句就能囊括素数的规律吗?
其实并不是,在判断素数之前,咱们还得将要判断的这个数 $n$ 转换成由 $n$ 个特定字符组成的字符串。什么意思呢?举个栗子:
假设这个 特定字符 是 1
。
要判断 4 是否为素数,就向正则输入 1111
;要判断 7,则输入 1111111
。
将表达式测试该字符串的结果取反,就表明这个数是否是素数。即:正则匹配成功为合数,匹配失败为素数。
解析
没错,这个正则验证的并不是数本身,而是字符出现次数是否为素数;也不是通过什么黑科技直接验证出现的次数是否为素数,而是尝试匹配合数,再将结果取反(毕竟除了合数就是素数)。了解了这一点再来理解这个表达式会清晰许多。
拆解
这个有意思的正则分为以下两个部分:
^1?$
^(11+?)\1+$
先看第一部分 ^1?$
,这是在匹配一个或零个字符 1。
这里的 ^
和 $
成对出现表明严格匹配中间的表达式,如果整个文本无法匹配上,那就全都不会匹配上(而不是匹配全文的其中一部分)。
这里其实是对 1
这种情况的特殊处理,并不是最重要的部分。
第二部分与第一部分使用 |
连接,即它们是或的关系,只有第一部分不能匹配时才会尝试匹配第二部分。
先看看这个分组吧 (11+?)
,这是匹配两个或多个字符 1,并且采用了 lazy 模式。
为什么是匹配两个或以上?
因为素数 $p$ 是一个对于任意一个 $n\in[2,p)$ 都不能把 p 给整除的数。
之后是 \1+
,其中 \1
表示动态匹配 group 1 所匹配到的内容,而 +
就表示可以匹配一次或多次。
是不是恍然大悟呢!
没错,这个正则就是在寻找是否有 $n$ 个 1
(这 $n$ 个 1
称为 group1),能够把整个字符串平均拆分成 $m$ 个 group1 。(其中 $n\in[2,+\infty)$ ,$m\in[1,+\infty)$)
也就是说从数学角度来讲,这个正则正在寻找是否有一个数 $n$ 能够被字符串的总长所整除! $m$ 即为商。
细节
第一部分中为什么要有 ?
是为了让正则对于处理空字符串时有更好的健壮性。(即输入空字符串应当匹配成功)
第二部分为什么要有 ?
这里的 ?
表示 lazy 匹配,是为了让正则表达式有更好的性能。
类比成算法即:在尝试整除的时候,从 2
开始尝试,而不是从 n-1
开始尝试。(n 是待验证的数)
同时是否采用 lazy 匹配时 group1 的内容也是不同的。lazy 匹配时 group1 是最小的因数(除 1 以外),非 lazy 时则是最大的因数(除本身以外)。
为什么使用字符 1
来匹配?
理论上使用任何字符都可行,只需要更改正则表达式中代表匹配 特定字符 的那一段。
例:使用 a
来匹配,正则为:^a?$|^(aa+?)\1+$
,当然此时你也应该用 n
个a
作为输入而不再是使用 1
了。