2008-03-23 2:04| 
16 Comments | 本文内容遵从 今天又学到一个牛B东西。你相信吗？正则表达式竟然可以用来判定素数，甚至可以用来解方程！下面这段正则表达式可以用来判断，一个字符串的长度是否为合数（假设这个字符串里全是字符'1'）：^1?$|^(11+?)\1+$
不信的话，把下面这段代码复制到你浏览器的地址栏里运行一下，True表示这个数为合数，False表示这个数为素数：
javascript:var st="1";for(var i=2;i<100;i++)document.write(i," ",/^1?$|^(11+?)\1+$/.test(st=st+"1"),"<br/>");document.close();
其实，它的原理很简单。加号表示匹配一次或多次（加上一个问号表示非贪婪模式），\1表示引用括号里的内容，头尾的^和$则避免了部分匹配的情况。这样，^(11+?)相当于枚举除数大小，而\1+$则用于检验整个字符串是否能按此大小恰好分完。如果除得尽，则匹配成功，字符串长度为合数。另外，前面的^1?$只是为了处理n=0或n=1时的特殊情况，而符号|则表示“或者”的意思。
采用同样的方法，我们还可以想出正则表达式其它一些类似的用途。比如，我们可以用这个正则表达式检查方程11x + 2y + 5z = 115是否有自然数解：^(.*)\1{10}(.*)\2{1}(.*)\3{4}$
正则表达式中，{x}表示和前面的内容匹配x次。只要用这个表达式去检测一个有115个字符的字符串，匹配成功则表示有自然数解。它的原理和上面的基本一样，我就不再重复了。
参考资料：http://blog.stevenlevithan.com/archives/algebra-with-regexes
16 条回复
您也随便说几句吧：
抢个沙发先..
记得有人证过正则表达式是图灵完备的
真是巨NB啊！
cool!!
正则很强大
效率很低下
O(n)的
iptables防火墙设置似乎也是图灵完全的
I'm interested in your school life.
[...] 从quhao那里，了解到这样一篇文章：牛B的正则表达式：素数判定与线性方程求解： 今天又学到一个牛B东西。你相信吗？正则表达式竟然可以用来判定素数，甚至可以用来解方程！下面这段正则表达式可以用来判断，一个字符串的长度是否为合数（假设这个字符串里全是字符’1′）： ^1?$|^(11+?)1+$ [...]
根据本文内容，我写了一篇分析文章。点击本条留言的网址即可查看。
正则表达式(非扩展)不是图灵完备的
[...] 我们之前已经见过了正则表达式的一些很特殊的用法。这里我们再来看一个：用正则表达式判断数的整除性。例如，下面这个表达式可以匹配01串S当且仅当S是一个可以被3整除的二进制数。 [...]
运行1000000的死机了！
牛B的正则表达式：整除性判定...
如何判定一个数能否被3整除? 比如6。
如果你有Python，可以在交互式解释器里面输入：
import re
print re.match(”1((10*1)|(01*0))*10*$”, “110″)!=None
......
牛B的正则表达式：整除性判定...
如何判定一个数能否被3整除? 比如6。
如果你有Python，可以在交互式解释器里面输入：
import re
print re.match(”1((10*1)|(01*0))*10*$”, “110″)!=None
......
如此牛逼啊～～～～
佩服～匹配规则看起来还是有些头疼～
nice work!
it seems re can do something more...