首页 > 编程语言 > 检查素数的正则表达式

检查素数的正则表达式

2010年7月23日 发表评论 阅读评论 14,063 人阅读    

一般来说,我们会使用正规表达式来做字符串匹配,今天在网上浏览的时候,看到了有人用正则表达式来检查一个数字是否为素数(质数),让我非常感兴趣,这个正则表达式如入所示:

检查素数与否的正则表达式

要使用这个正规则表达式,你需要把自然数转成多个1的字符串,如:2 要写成 “11”, 3 要写成 “111”, 17 要写成“11111111111111111”,这种工作使用一些脚本语言可以轻松的完成。

一开始我对这个表达式持怀疑态度,但仔细研究了一下这个表达式,发现是非常合理的,下面,让我带你来细细剖析一下是这个表达式的工作原理。

首先,我们看到这个表达式中有“|”,也就是说这个表达式可以分成两个部分:/^1?$/ 和 /^(11+?)\1+$/

  • 第一部分:/^1?$/, 这个部分相信不用我多说了,其表示匹配“空串”以及字串中只有一个“1”的字符串。
  • 第二部分:/^(11+?)\1+$/,这个部分是整个表达式的关键部分。其可以分成两个部分,(11+?)\1+$,前半部很简单了,匹配以“11”开头的并重复0或n个1的字符串,后面的部分意思是把前半部分作为一个字串去匹配还剩下的字符串1次或多次(这句话的意思是——剩余的字串的1的个数要是前面字串1个数的整数倍)。

可见这个正规则表达式是取非素数,要得到素数还得要对整个表达式求反。通过上面的分析,我们知道,第二部分是最重要的,对于第二部分,举几个例子,

示例一:判断自然数8。我们可以知道,8转成我们的格式就是“11111111”,对于(11+?),其匹配了“11”,于是还剩下“111111”,而\1+$正好匹配了剩下的“111111”,因为,“11”这个模式在“111111”出现了三次,符合模式匹配,返回true。所以,匹配成功,于是这个数不是质数。

示例二:判断自然数11。转成我们需要的格式是“11111111111”(十一个1),对于(11+?),其匹配了“11”(前两个1),还剩下“111111111”(九个1),而\1+$无法为“11”匹配那“九个1”,因为“11”这个模式并没有在“九个1”这个串中正好出现N次。于是,我们的正则表达式引擎会尝试下一种方法,先匹配“111”(前三个1),然后把“111”作为模式去匹配剩下的“11111111”(八个1),很明显,那“八个1”并没有匹配“三个1”多次。所以,引擎会继续向下尝试……直至尝试所有可能都无法匹配成功。所以11是素数。

通过示例二,我们可以得到这样的等价数算算法,正则表达式会匹配这若干个1中有没有出现“二个1”的整数倍,“三个1”的整数倍,“四个1”的整数倍……,而,这正好是我们需要的算素数的算法。现在大家明白了吧。

下面,我们用perl来使用这个正规则表达式不停地输出素数:(关于perl的语法我就不多说了,请注意表达式前的取反操作符)

perl -e'$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print"$_ "while ++$_'

另外,让我们来举一反三,根据上述的这种方法,我们甚至可以用正则表达式来求证某方式是否有解,如:

  • 二元方程:17x + 12y = 51   判断其是否有解的正则表达式是:^(.*)\1{16}(.*)\2{11}$
  • 三元方程:11x + 2y + 5z = 115 判断其是否有解的正则表达式是:^(.*)\1{10}(.*)\2{1}(.*)\3{4}$

大家不妨自己做做练习,为什么上述的两个正则表达式可以判断方程是否有解。如果无法参透其中的奥妙的话,你可以读读这篇英文文章

(全文完)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell.cn ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
分类: 编程语言 标签:
好烂啊有点差凑合看看还不错很精彩 (36 人打了分,平均分: 4.67 )
Loading ... Loading ...
  1. poly
    2010年7月23日09:26 | #1

    我嘞个去~
    这个太牛逼了~

  2. 2010年7月23日09:43 | #2

    博主这样解释这个正则表达式欠妥啊,第一部分/^1?$/中?号表示匹配前面的字母或子表达式0次或1次,所以就是匹配没有1和一个1的情况,即n=0或n=1。
    第二部分/^(11+?)\1+$/ ,^和$应该是匹配开始和结束符。
    整个表达式应该匹配成功表示不是素数,反之是素数。

  3. 水银
    2010年7月23日10:11 | #3

    ^不是反的意思….. 是表示匹配起始
    楼上说的对,表达式是用来 if(!reg.test(string)) then 素数

  4. 2010年7月23日10:12 | #4

    兄弟是不是理解错了? 还是我理解错了, 如果这个正则是perl的话, 那^应该是指匹配开始, 而不是求反.

  5. 2010年7月23日10:34 | #5

    ?在perl中表示非贪婪匹配,+标识至少匹配一次,因此11+表示匹配一次“11”
    \1表示匹配前面匹配的第一个group,因此/^(11+?)\1+$/表示匹配1个或多个“11”,而/^1?$/包含了一个1的情况

    至于这个正则表达式为何能够匹配素数…研究中…

  6. 2010年7月23日11:04 | #6

    @lobatt
    这个是正则表达式引擎匹配的工作原理决定的,(11+?)先匹配一个11,看后面的\1+能不能匹配,相当于看能不能被2整除,不能的话(11+?)下来就会匹配111,再看能不能匹配,相当于看能不能被3整除,依次进行,这就是判定素数最朴素的方法啊!若中间有一次匹配成功了,就代表能被某个数整除,就不是素数,若一直到最后都没有匹配成功,则是素数。

  7. 2010年7月23日11:25 | #7

    @Crane
    忘了这茬了…才体会到这个正则的牛鼻之处…

  8. poly
    2010年7月23日11:53 | #8

    嗯,博主的解释的确有误~
    另外第一部分匹配的应该是“空”或者“1”~
    这两种情况也非素数~

  9. 依云
    2010年7月23日12:03 | #9

    很神奇,不过速度实在是太慢了点。

    • 2010年7月23日14:26 | #10

      谢谢大家的评论以及指正。的确如此,这个表达式其实是判断非质数的,需要对整个表达式取反(关于那个^表示开始,而不是取反),我写文章的时候疏忽了(已经修正了)。关于其原理,我个人以为我描述地很清楚了。谢谢大家的留言。

  10. 2010年7月23日14:28 | #11

    真的很牛哦,能想出这种办法,太牛了

  11. hrpenf
    2010年7月23日15:36 | #12

    nb,太有想法了,这种思维转换是需要学习的地方

  12. 2010年7月23日18:06 | #13

    写出来的是牛人,分享得这么清楚的也是牛人,呵呵。深圳电信,打开你这里,要很长时间呢。

  13. 2010年7月23日19:13 | #14

    @依云
    因为是模拟人肉测试嘛…

  14. d3m
    2010年7月23日22:27 | #15

    为什么我的两个浏览器看到的那段perl代码都是:
    perl -e’$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print"$_ "while ++$_’ 呢?
    看正常的这个能显示出来不:
    perl -e’$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print”$_ “while ++$_’
    运行起来果然不是一般的慢..

  15. 2010年7月23日23:33 | #16

    @d3m
    不好意思,这可能是Wordpress的问题。现已修正。谢谢指正。

  16. akira
    2010年7月26日14:17 | #17

    任何有限状态的推导理论上来讲都能转换为证则表达式

    对于一个特定素数来说,其因子个数是有限的,对于一个多元方程自然数解也满足这个条件~

  17. 2010年7月27日23:55 | #18

    学习了,很有意思的一个话题!

  18. 2010年7月28日23:08 | #19

    这个太NB了。。。

  19. 2010年7月29日20:26 | #20

    有意思。

  20. jruv
    2010年8月13日16:33 | #21

    这个表达式相当NB,第一部分/^1?$/不用说很显然就是考虑n=1或n=0的情况, 第二部分/^(11+?)\1+$/实际上是利用regexp解释器来寻找该数值n的第一个可以被整除的因子。找到了就是匹配, 也就是非质素。 其中子匹配(11+?)就是该数值n的第一个可以被整除的因子

  21. 2011年3月24日15:15 | #22

    perl正则表达式表示能力已经超越正则预言了。素数个1显然不是正则语言。
    提问:perl正则表达式能力等效于图灵机么?

  22. biohuang
    2011年7月25日10:03 | #23

    @biran

    perl正则表达式表示能力没有超越正则预言。

    素数个1显然不是正则语言。但该表达式寻找到的是合数个1,这是正则语言。取反条件表达式已经不是正则表达式的能力了,是perl的能力,后者等价于图灵机。

  23. dunxp
    2011年8月26日21:30 | #24

    最后两个题应该是检查有无非负整数解

    另外,为什么不用^(.*){17}(.*){12}$呢

  24. 2012年1月6日17:43 | #25

    Crane :
    @lobatt
    这个是正则表达式引擎匹配的工作原理决定的,(11+?)先匹配一个11,看后面的\1+能不能匹配,相当于看能不能被2整除,不能的话(11+?)下来就会匹配111,再看能不能匹配,相当于看能不能被3整除,依次进行,这就是判定素数最朴素的方法啊!若中间有一次匹配成功了,就代表能被某个数整除,就不是素数,若一直到最后都没有匹配成功,则是素数。

  25. Honkhat
    2012年4月22日15:19 | #26

    ..一点也不NB,没新意。归根结底还是 挨个判断。。

  26. mihello
    2012年9月7日17:01 | #27

    另辟蹊径,不过效率方面我第一反应是不会高。

  27. ethantsien
    2012年10月14日05:26 | #28

    这东西速度太慢,我想不到什么时候会用到它,哪个编程语言会不支持算数运算?

  28. hythyt9898
    2013年2月4日15:16 | #29

    有一点觉得不明白,子串(11+?)直接用(11+)不就行了?+号不就表示1个或n个1嘛,为什么多用一个”?”

  29. raintiny
    2013年6月2日14:17 | #30

    这不就是根据素数的定义来的。。。

  30. vapour
    2014年1月23日15:20 | #31

    @hythyt9898 加?表示非贪婪匹配。

  31. biohuang
    2014年3月3日11:18 | #32

    @biran
    呃,那时perl刚入门,只知道perl正则表达式的基本用法。perl的正则表达式引擎远远超过了正则语言的表达力,不过似乎还表达不了上下文有关语言吧。

  1. 2010年7月24日19:23 | #1
  2. 2010年7月25日12:24 | #2
  3. 2010年7月26日01:49 | #3
  4. 2010年7月26日22:15 | #4
  5. 2010年7月27日11:33 | #5
  6. 2010年9月21日14:15 | #6
  7. 2011年3月1日23:59 | #7
  8. 2011年7月21日12:40 | #8
  9. 2011年7月21日19:24 | #9
  10. 2011年7月27日18:51 | #10
  11. 2011年12月26日11:21 | #11
  12. 2012年5月16日15:55 | #12
  13. 2013年8月14日09:32 | #13
  14. 2013年11月10日16:52 | #14
  15. 2013年11月10日17:01 | #15
  16. 2014年3月21日19:23 | #16