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