检查素数的正则表达式

marz posted @ Aug 11, 2010 07:12:14 AM in regex with tags RegEx prime number js , 1822 readers

 

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

检查素数的正则表达式/^1?$|^(11+?) +$/

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

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

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

  • 第一部分:/^1?$/ 这个部分相信不用我多说了,其表示匹配“空串”以及字串中只有一个“1”的字符串。
  • 第二部分:/^(11+?)\1+$/,这个部分是整个表达式的关键部分。其可以分成两个部分,(11+?) \1+$,前半部很简单了,匹配以“11”开头的并重复0n1的字符串,后面的部分意思是把前半部分作为一个字串去匹配还剩下的字符串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}$

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

 

源文档 <http://www.google.com/reader/view/>

meidir said:
Sep 14, 2022 10:01:30 PM

a extremely superb webpage. a realy educational in addition to a an extremely superior position. i’m a sucker for the. Remove tree Sacramento

 

=================

 

We have not too long ago started out any website, the knowledge an individual offer on this web site provides aided myself tremendously. Thank you regarding your entire moment & perform. Stump removal sacramento county

 

=================

 

That is a good write-up When i viewed on account of write about the item. Really it is what exactly I need to to discover trust with foreseeable future you might go on intended for giving a really fantastic write-up. Kingdom tree service

 

=================

 

Great submit, the an extremely great website which you have the following, maintain the nice perform, will probably be again. what to wear to a pageant

 

=====================

 

I’m empowered together with the surpassing plus preachy detailing for you to decorate such minimal timing. how much is it to rent a water slide

 

=====================

 

This really is awesome publish as well as i love to to learn this particular publish. your website is actually wonderful and also you possess great personnel inside your weblog. good discussing stay the best. how much does it cost to rent an inflatable obstacle course

 

======================

 

Positive site, where did u produce the information with this posting?I have read a several articles on your own website now, and I enjoy your style. Thanks a million and please maintain the effective work. Fire damage Spokane wa

 

======================

 

Positive site, where did u come up with the information on this posting?I have read a several articles on your own website now, and I enjoy your style. Thanks a million and please keep up the effective work. Bounce house rentals Sacramento

 

======================

 

Positive site, where did u come up with the information on this posting?I've read a several articles in your website now, and I enjoy your style. Thanks a million and please maintain the effective work. Bounce house sacramento

 

======================

 

Positive site, where did u develop the info on this posting?I have read a some of the articles on your own website now, and I really like your style. Thanks a million and please keep up the effective work. Is SEO worth it in 2022

 

=====================

 

Positive site, where did u develop the information with this posting?I have read a some of the articles on your website now, and I enjoy your style. Thanks a million and please continue the effective work. flower delivery seattle, WA

 

=====================

 

Positive site, where did u come up with the info with this posting?I've read a some of the articles in your website now, and I enjoy your style. Thanks a million and please continue the effective work. commercial window tinting sacramento

 

=====================

 

I have read your article couple of times because your views are on my own for the most part. It is great content for every reader. sell my house fast seattle washington

meidir said:
Sep 15, 2022 10:15:09 PM

Freezing consideration perhaps it is an understanding to create could possibly help everybody else is having troubles searching though My group is some unclear a lot more i am permitted to get details and even communications information at these. What is SAP Fiori

meidir said:
Sep 15, 2022 10:15:31 PM

Outstanding submit, travelled in advance and also book marked your internet site. My partner and i can’t hold out to learn a lot more coming from an individual. Téléchargement de vidéos TikTok

meidir said:
Sep 19, 2022 07:01:29 PM

Very good Article, We are a major believer throughout putting up responses in internet sites for you to let the web site freelance writers be aware that they’ve included a thing helpful for you to virtual reality! Excursions in agadir

meidir said:
Sep 20, 2022 12:38:00 AM

Because the New, My organization is in the long term searching online intended for article content which really may be for benefit my family. Many thanks so much. Descargar Instalador APk

meidir said:
Sep 20, 2022 12:38:21 AM

As the New, My organization is in the long term searching online created for article content which really could be for assist with my family. Thanks so much. waxing las olas

seo service london said:
Oct 09, 2023 01:47:21 PM

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well..

저금통주소 said:
Oct 15, 2023 05:56:22 PM

나는 모든 것을 확실히 즐기고 있습니다. 훌륭한 웹 사이트이자 좋은 공유입니다. 감사합니다. 잘 했어! 여러분은 훌륭한 블로그를 만들고 훌륭한 콘텐츠를 가지고 있습니다. 좋은 일을 계속하십시오.
[url=https://www.xn--jj0b407a9oan0scjb083aoqd.com/]저금통주소[/url]

저금통주소 said:
Oct 15, 2023 05:58:28 PM
당신의 기사는 정말 사랑스러워 보입니다. 여기 당신이 좋아할만한 사이트 링크가 있습니다.
[https://www.xn--jj0b407a9oan0scjb083aoqd.com/ 저금통주소]
 

 

707도메인 said:
Oct 15, 2023 06:06:38 PM

터키에서 온라인 스포츠 베팅을 할 수있는 베팅 사이트 목록은 바로 방문하십시오.

asdas said:
Oct 15, 2023 06:36:28 PM

터키에서 온라인 스포츠 베팅을 할 수있는 베팅 사이트 목록은 바로 방문하십시오. <a href="https://xn--hs0by0egti38za.com/">꽁머니</a>

asdas said:
Oct 16, 2023 06:39:20 PM

Thanks for providing recent updates regarding the concern, I look forward to read more. <a href="https://xn--hs0by0egti38za.com/">꽁머니</a>

asdas said:
Oct 16, 2023 08:34:11 PM

There is definately a great deal to know about this subject. I like all of the points you've made <a href="https://www.momobetr.com/">모모벳</a>

asdas said:
Oct 16, 2023 09:00:22 PM

Hi buddies, it is great written piece entirely defined, continue the good work constantl
<a href="https://www.nomnomnombet.com/">놈놈놈 토토</a>

asdas said:
Oct 16, 2023 09:29:59 PM

Thanks for providing recent updates regarding the concern, I look forward to read more. <a href="https://www.totoyojung.com/">토토랭킹</a>

뉴토끼 said:
Oct 18, 2023 08:20:00 PM

주목할만한 기사, 특히 유용합니다! 나는 이것에서 조용히 시작했고 더 잘 알게되고 있습니다! 기쁨, 계속해서 더 인상적

sophia said:
Oct 19, 2023 12:44:25 AM

Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!.. UFABETเว็บตรงจากบริษัทแม่

sophia said:
Oct 19, 2023 02:59:14 AM

Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!.. แทงบอลออนไลน์ฟรีUFABET

sophia said:
Oct 19, 2023 12:35:57 PM

Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject. เว็บพนันบอลดีที่สุด pantip

sophia said:
Oct 19, 2023 02:06:28 PM

Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!.. UFABETเว็บพนันบอลไม่ผ่านเอเย่นต์

Seo Service Cananda said:
Oct 21, 2023 03:53:08 PM

Hi, I also visit this site daily; this webpage is truly pleasant & users are openly sharing fastidious thoughts

툰코 said:
Nov 02, 2023 03:27:55 PM

I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post <a href="https://start.me/p/jj6MRa">툰코</a>

카지노사이트 said:
Nov 23, 2023 03:31:50 PM

이 목표에 도달했을 때의 사실을 생각해보십시오.

seoo said:
Dec 11, 2023 05:12:21 AM

I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post.Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.Thanks 시흥출장안마

seoo said:
Dec 13, 2023 01:22:06 PM

I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business.You are truly well informed and very intelligent. You wrote something that people could understand and made the subject intriguing for everyone. Really, great blog you have got here.Nice knowledge gaining article. This post is really the best on this valuable topic.This is my first time visit here. From the tons of comments on your articles,I guess I am not only one having all the enjoyment right here! 영등포마사지

마사지 said:
Jan 04, 2024 04:29:22 PM

i read your article its good for humanity thanks for sharing this its very informative

sophia said:
Jan 18, 2024 08:54:30 PM

Very interesting blog. Alot of blogs I see these days don't really provide anything that I'm interested in, but I'm most definately interested in this one. Just thought that I would post and let you know. ufabet เว็บตรงทางเข้า

sophia said:
Jan 19, 2024 03:08:24 AM

This is my first time visit here. From the tons of comments on your articles,I guess I am not only one having all the enjoyment right here! ufabet เข้าสู่ระบบเว็บตรง

seo said:
Jan 22, 2024 03:15:23 AM

Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work.I was reading some of your content on this website and I conceive this internet site is really informative ! Keep on putting up. Non Segregated Phase Bus

seoo said:
Jan 26, 2024 04:39:46 AM

You make so many great points here that I read your article a couple of times. I wil be checking back soon to find out what additional posts you include. 42mm High Torque Stepper Motors

seo said:
Jan 27, 2024 03:51:26 AM

При регистрации на официальном сайте 1xBet пользователь может выбрать из различных методов регистрации, включая регистрацию с помощью номера телефона, электронной почты или аккаунта в социальных сетях. В каждом из этих случаев будет предоставлено поле для ввода промокода 1xBet. Если промокод действителен, игрок получит дополнительный бонус после активации основного бонуса. https://sputnikspb.com/catalog/pgs/?1xbet_promokod_pri_registracii_bonus.html

카지노 커뮤니티 said:
Feb 05, 2024 06:04:02 PM

Thank you so much as you have been willing to share information with us. We will forever admire all you have done here because you have made my work as easy as ABC.

온라인카지노 said:
Feb 05, 2024 07:37:07 PM

I am very happy to discover your post as it will become on top in my collection of favorite blogs to visit

토토사이트추천 said:
Feb 06, 2024 03:53:14 PM

Pleasant article.Think so new type of elements have incorporated into your article. Sitting tight for your next article

우리카지노 said:
Feb 06, 2024 05:23:24 PM

Amazing knowledge and I like to share this kind of information with my friends and hope they like it they why I do.

seoo said:
Feb 07, 2024 03:51:40 PM

I havent any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us.Hello, this weekend is good for me, since this time i am reading this enormous informative article here at my home. Bluetooth lock with Cloud Platform and task Authorization

seoo said:
Feb 10, 2024 03:42:09 AM

Very nice article, I enjoyed reading your post, very nice share, I want to twit this to my followers. Thanks!.Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!Thanks immediate momentum website

Jane Maria said:
Feb 10, 2024 07:34:49 PM

you use a fantastic weblog here! if you’d like to cook some invite posts in my blog? güvenilir bahis siteleri

먹튀검증 said:
Feb 12, 2024 08:00:01 PM

I like review sites which grasp the cost of conveying the fantastic helpful asset for nothing out of pocket. I genuinely revered perusing your posting. Much obliged to you

카지노사이트추천 said:
Feb 13, 2024 07:35:01 PM

I have read your article; it is very informative and helpful for me. I admire the valuable information you offer in your articles. Thanks for posting it

seo said:
Feb 15, 2024 05:29:27 PM

Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome!This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value. Im glad to have found this post as its such an interesting one! I am always on the lookout for quality posts and articles so i suppose im lucky to have found this! I hope you will be adding more in the future...Thanks for taking the time to discuss this, I feel strongly that love and read more on this topic. immediate momentum

카지노 올인토토 said:
Mar 05, 2024 02:03:44 PM

You might comment on the order system of the blog. You should chat it's splendid. Your blog audit would swell up your visitors. I was very pleased to find this site.I wanted to thank you for this great read!!

온라인 슬롯 said:
Mar 05, 2024 02:20:40 PM

I have bookmarked your website because this site contains valuable information in it. 

바카라 사이트 said:
Mar 05, 2024 02:42:20 PM

This is actually the kind of information I have been trying to find. Thank you for writing this information.

온라인바카라사이트 said:
Mar 05, 2024 04:55:15 PM

와우, 멋진 게시물입니다. 너무 많은 정보학을 찾았습니다.

바카라사이트 said:
Mar 05, 2024 10:38:46 PM

I ought to declare scarcely that its astonishing! The blog is instructive additionally dependably manufacture astonishing entities

온라인 카지노 said:
Mar 06, 2024 02:37:03 PM

Great and an informative article! this wonderful post

스포츠중계 said:
Mar 06, 2024 02:38:31 PM

This was a really wonderful post. Thank you for providing these details

바카라 사이트 said:
Mar 06, 2024 03:18:11 PM

I am very happy to discover your post as it will become on top in my collection of favorite blogs to visit.

먹튀검증 said:
Mar 06, 2024 03:27:44 PM

Hello. Great job. I did not anticipate this. This is a splendid articles

온라인카지노 said:
Mar 06, 2024 03:36:57 PM

This article is one of the best in the history of articles. I'm a antique 'Article' collector and I sometimes read them interesting

먹튀검증 said:
Mar 06, 2024 04:27:43 PM

I  have read your article; it is very informative and helpful for me. I admire the valuable information you offer in your articles. Thanks for posting it.  

카지노사이트추천 said:
Mar 06, 2024 05:02:06 PM

It is an excellent blog, I have ever seen. I found all the material on this blog utmost unique and well written. And, I have decided to visit it again and again

토토검증사이트 said:
Mar 06, 2024 05:47:39 PM

I would recommend my profile is important to me, I invite you to discuss this topic

토토사이트 said:
Mar 06, 2024 06:11:05 PM

This is a truly good site post. Not too many people would actually, the way you just did. I am really impressed that there is so much information about this subject that have been uncovered and you’ve done your best, with so much class. If wanted to know more about green smoke reviews, than by all means come in and check our stuff.

먹튀검증 said:
Mar 06, 2024 07:00:06 PM

Wow, What an Outstanding post I found

카지노사이트 said:
Mar 06, 2024 08:39:35 PM

What a really awesome post this is. Truly, one of the best posts I've ever witnessed to see in my whole life. Wow, just keep it up

카지노사이트 said:
Mar 06, 2024 09:43:07 PM

I really like this blog. Thanks for sharing.

토토사이트추천 said:
Mar 06, 2024 10:23:15 PM

I have bookmarked your website because this site contains valuable information in it. 

먹튀검증 said:
Mar 12, 2024 04:33:46 PM

No.1 먹튀검증 사이트, 먹튀사이트, 검증사이트, 토토사이트, 안전사이트, 메이저사이트, 안전놀이터 정보를 제공하고 있습니다. 먹튀해방으로 여러분들의 자산을 지켜 드리겠습니다. 먹튀검증 전문 커뮤니티 먹튀클린만 믿으세요!!


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter