继两年多前我写过一篇用正则表达式匹配3的任意倍数后，今天再给大家带来正则表达式另外一个骚操作。如何判定一个数n是否是质数，根据素数的定义，只要看n能否被1到n之间数整除可以了。这个正则表达式可以表示为以下代码。判断一个数是否是素数的方式有很多种，比较快的有基于费马小定理的Miller-Rabin算法，其次有筛选法，再次可以暴力试除。抛开它的实用性不谈，不得不说这确实是一个非常有意思的问题。
继两年多前我写过一篇用正则表达式匹配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的方式在正则表达式中使用前面第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个1return truereturn false
从伪代码可以看出，这里其实和我们直接用暴力试除法判断素数是一样的。
性能如何？
判断一个数是否是素数的方式有很多种，比较快的有基于费马小定理的Miller-Rabin算法，其次有筛选法，再次可以暴力试除。其实也可以看出，用正则表达式来测试素数的方法本质上属于暴力求解的方法，但你在暴力求解前还得做数字n到n个1字符串的转化，会消耗更多的性能和存储空间，所以性能肯定远不如暴力试除的方式判定素数。
总结
用正则表达式来判定一个数是否是素数，和我之前写过的用正则表达式匹配3的任意倍数一样很牛X。
抛开它的实用性不谈，不得不说这确实是一个非常有意思的问题。在持续学习的过程中，我发现有一些知识点并不具备实际使用的价值，但他们却能触发我们的思考，帮我们理解背后更深层次的原理，或许这就是他们的价值所在。
本文来自https://blog.csdn.net/xindoo
