检查素数的正则表达式分享

这个正则表达式如入所示：


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

要使用这个正规则表达式，你需要把自然数转成多个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}$

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

赞 (0)

相关推荐

  • JS 用6N±1法求素数 实例教程

    用6N±1法求素数 任何一个自然数,总可以表示成为如下的形式之一: 6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,-) 显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数.所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数). 根据上述分析,我们可以构造另一面筛子,只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度. 以下代码需要自然数大于

  • 用正则表达式来判断素数的代码

    复制代码 代码如下: import re def is_prime(num): return not re.match(r"^1?$|^(11+?)\1+$", '1' * num) 这个正则表达式实际上表示所有合数长度的"1"串(还包括特例"1"). (11+?)表示所有大于等于2的整数,后面接着的\1+表示重复一次以上--这不就是所有合数吗--

  • php 求质素（素数） 的实现代码

    复制代码 代码如下: <?php class timer { var $time_start; var $time_end; function __construct() { $this->time_start = 0; $this->time_end = 0; } function timer() { $this->__construct(); } function start() { list($usec,$sec) = explode(" ",microt

  • 检查素数的正则表达式分享

    检查素数的正则表达式分享

    这个正则表达式如入所示: 检查素数与否的正则表达式 要使用这个正规则表达式,你需要把自然数转成多个1的字符串,如:2 要写成 "11", 3 要写成 "111", 17 要写成"11111111111111111",这种工作使用一些脚本语言可以轻松的完成. 一开始我对这个表达式持怀疑态度,但仔细研究了一下这个表达式,发现是非常合理的,下面,让我带你来细细剖析一下是这个表达式的工作原理. 首先,我们看到这个表达式中有"|",也就

  • 史上最详细的js日期正则表达式分享

    最简单的正则 如 : /d{4}-/d{2}-/d{2}但是实际情况却不是那么简单,,要考虑,有效性和闰年等问题..... 对于日期的有效范围,不同的应用场景会有所不同.MSDN中定义的DateTime对象的有效范围是:0001-01-01 00:00:00到9999-12-31 23:59:59. UNIX时间戳的0按照ISO 8601规范为 :1970-01-01T00:00:00Z. 先考虑与年份无关的前三条规则,年份可统一写作 (?!0000)[0-9]{4} 下面仅考虑月和日的正则 1

  • C#匹配中文字符串的4种正则表达式分享

    本文介绍在C#中使用匹配中文的正则表达式,包括纯中文.有中文.中文开头.中文结尾等几个正则表达式示例.在正则表达式中,中文可以通过Unicode编码来确定正则表达式范围. 在C#中,匹配中文的正则表达式用Unicode来表示时,范围是: [\u4e00-\u9fa5].所以,在此基础上,我们可以得到如下一些正则表达式. 1.匹配字符串全部是中文字符的正则表达式 复制代码 代码如下: "^[\u4e00-\u9fa5]+$" 说明:"^"表示字符串开头,"$

  • c#求范围内素数的示例分享(c#求素数)

    程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数. 复制代码 代码如下: #include <stdio.h>#include <math.h> void main(){    int low,high,t=0;    printf("请输入你想寻找素数的范围(例如10~100,输入10 100)\n");    scanf("%d %d",&low,&high);

  • php半小时精通正则表达式

    想必很多人都对正则表达式都头疼.今天,我以我的认识,加上网上一些文章,希望用常人都可以理解的表达方式.来和大家分享学习经验. 开篇,还是得说说 ^ 和 $ 他们是分别用来匹配字符串的开始和结束,以下分别举例说明: "^The":开头一定要有"The"字符串: "of despair$":结尾一定要有"of despair" 的字符串: 那么, "^abc$":就是要求以abc开头和以abc结尾的字符串,实际

  • 深入php 正则表达式的学习探讨

    1.入门简介 简单的说,正则表达式是一种可以用于模式匹配和替换的强有力的工具.我们可以在几乎所有的基于UNIX系统的工具中找到正则表达式的身影,例如,vi编辑器,Perl或PHP脚本语言,以及awk或sed shell程序等.此外,象JavaScript这种客户端的脚本语言也提供了对正则表达式的支持.由此可见,正则表达式已经超出了某种语言或某个系统的局限,成为人们广为接受的概念和功能. 正则表达式可以让用户通过使用一系列的特殊字符构建匹配模式,然后把匹配模式与数据文件.程序输入以及WEB页面的表

  • php正则表达式的基本语法总结

    首先,让我们看看两个特别的字符:'^' 和 '$' 他们是分别用来匹配字符串的开始和结束,一下分别举例说明 "^The": 匹配以 "The"开头的字符串; "of despair$": 匹配以 "of despair" 结尾的字符串; "^abc$": 匹配以abc开头和以abc结尾的字符串,实际上是只有abc与之匹配 "notice": 匹配包含notice的字符串 你可以看见如果你

  • php中看实例学正则表达式

    看实例学正则表达式    首先,让我们看看两个特别的字符:'^' 和 '$' 他们是分别用来匹配字符串的开始和结束,一下分别举例说明: 首先,让我们看看两个特别的字符:'^' 和 '$' 他们是分别用来匹配字符串的开始和结束,一下分别举例说明: "^The": 匹配以 "The"开头的字符串; "of despair$": 匹配以 "of despair" 结尾的字符串; "^abc$": 匹配以abc开头

  • PHP webshell检查工具 python实现代码

    1.使用方法:find.py 目录名称 2. 主要是采用python正则表达式来匹配的,可以在keywords中添加自己定义的正则,格式: ["eval\(\$\_POST","发现PHP一句话木马!"] #前面为正则,后面为对这个正则的描述,会在日志中显示. 3.修改下文件后缀和关键字的正则表达式就可以成为其他语言的webshell检查工具了,^_^. 4.开发环境是windows xp+ActivePython 2.6.2.2,家里电脑没有Linux环境,懒得装

  • pyCharm 实现关闭代码检查

    第一步 关闭代码拼写检查 setting–>Inspections–>Spelling–>Typo,取消勾选: 第二步 关闭代码风格校验 setting–>Inspections–>Python–>PEP8: 补充知识:如何关闭Pycharm中的show variables 每次运行完程序都会自动弹出show variables的框,非常烦躁,每次都要手动关闭,现在终于找到了解决方法: 以上这篇pyCharm 实现关闭代码检查就是小编分享给大家的全部内容了,希望能给大家

随机推荐