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

深碍√TFBOYSˉ_ 2021-09-25 07:28 139阅读 0赞

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

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

当我看到这个正则表达式，了解到它的作用后并试用后的第一反应  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]

不过它的使用方式比较特殊，如果想校验数字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的方式在正则表达式中使用前面第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字符串的转化，会消耗更多的性能和存储空间，所以性能肯定远不如暴力试除的方式判定素数。

## 总结 ##

用正则表达式来判定一个数是否是素数，和我之前写过的用[正则表达式匹配3的任意倍数][3]一样很牛X。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 1]

抛开它的实用性不谈，不得不说这确实是一个非常有意思的问题。**在持续学习的过程中，我发现有一些知识点并不具备实际使用的价值，但他们却能触发我们的思考，帮我们理解背后更深层次的原理，或许这就是他们的价值所在。**

[3]: https://blog.csdn.net/xindoo/article/details/102643270
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/0a37a57301de48fa9ef9aa513e6a32a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/f97b22b30a9a43be9136e993e8e3e984.png