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

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

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

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

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

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


  

 

  
1
  
2
  
3
 

看到这里，估计你也非常想知道为什么^(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 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

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

性能如何？

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

总结

用正则表达式来判定一个数是否是素数，和我之前写过的用正则表达式匹配3的任意倍数一样很牛X。

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

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/115826620