继两年多前我写过一篇用正则表达式匹配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个1 return truereturn false 从伪代码能够看出，这里其实和咱们间接用暴力试除法判断素数是一样的。
性能如何？
判断一个数是否是素数的形式有很多种，比拟快的有基于费马小定理的Miller-Rabin算法，其次有筛选法，再次能够暴力试除。其实也能够看出，用正则表达式来测试素数的办法实质上属于暴力求解的办法，但你在暴力求解前还得做数字n到n个1字符串的转化，会耗费更多的性能和存储空间，所以性能必定远不如暴力试除的形式断定素数。
总结
用正则表达式来断定一个数是否是素数，和我之前写过的用正则表达式匹配3的任意倍数一样很牛X。
抛开它的实用性不谈，不得不说这的确是一个十分有意思的问题。在继续学习的过程中，我发现有一些知识点并不具备理论应用的价值，但他们却能触发咱们的思考，帮咱们了解背地更深层次的原理，或者这就是他们的价值所在。