如何用正则表达式来检测一个数是否是素数

Z时代
2024-01-10
分类：综合

继两年多前我写过一篇用正则表达式匹配3的任意倍数后，今天再给大家带来正则表达式另外一个骚操作。

学过正则表达式的人或多或少知道正则表达式的强大功能，但用正则表达式来校验一个数是否是素数还是合数，听起来似乎也不大可能。但我前两天在查阅正则表达式相关的资料时，真的发现了这个可以校验是否是素数的神奇正则表达式 ^(11+?)1+$。

当我看到这个正则表达式，了解到它的作用后并试用后的第一反应

不过它的使用方式比较特殊，如果想校验数字n是否是素数，就得先把n转化为n个1的字符串(比如是11，就得先把11转成"11111111111")，然后尝试用 ^(11+?)1+$，如果匹配成功，说明这个数是合数，大家可以在chrome的控制台尝试执行下下面两行js代码。

var rgx =new RegExp(/^(11+?)1+$/)
rgx.test("11111111111")

看到这里，估计你也非常想知道为什么^(11+?)1+$能完成素数的校验，它的原理是啥？其实它背后的原理并不难理解，要理解这个正则表达式，我们首先理解质数以及它的性质，其次了解一个正则表达式的基本用法即可。

何为质数

质数的定义是：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。如何判定一个数n是否是质数，根据素数的定义，只要看n能否被1到n之间数整除可以了。实际上^(11+?)1+$也是用的同样的原理。

捕获和反向引用

要理解这个正则表达式，我们先得理解正则引擎的捕获和反向引用的功能。在NFA驱动的正则引擎中可以实现很多复杂的功能，捕获和反向引用。

捕获是指正则引擎可以将()中匹配的内容保存起来，反向引用是指通过

的方式在正则表达式中使用前面第n个()里匹配到大内容。

回到这个正则表达式上，(11+)可以匹配到任意大于等于2个数的1，1反向引用了(11+)所匹配到的内容，所以二者结合起来(11+)1能匹配到2n个1(n大于等于2)，所以如果能被这个正则表达式匹配到，那他肯定是一个合数，因为至少可以被2整除。那么不能匹配的一定是合数？

这里还不足以下定论，因为这里还判断不了3n……，其实我们只要在/1后+就可以了。

这个正则表达式可以表示为以下代码。

for i from 2 to n：
    for j from 2 to n：
        if 该字符串是i*j个1
            return true
return false

从伪代码可以看出，这里其实和我们直接用暴力试除法判断素数是一样的。

性能如何？

判断一个数是否是素数的方式有很多种，比较快的有基于费马小定理的Miller-Rabin算法，其次有筛选法，再次可以暴力试除。其实也可以看出，用正则表达式来测试素数的方法本质上属于暴力求解的方法，但你在暴力求解前还得做数字n到n个1字符串的转化，会消耗更多的性能和存储空间，所以性能肯定远不如暴力试除的方式判定素数。