Find primes in regexp

Posted by Jonas Elfström Fri, 30 Mar 2007 05:33:00 GMT

In an earlier post the example code did find prime numbers. Recently I stumbled over a really cool regexp hack that also deals with primes. This is how you execute that regexp in Ruby:

puts 'Prime' unless ('1' * 43) =~ /^1$|^(11+?)\1+$/

Change 43 to whatever you like and you will get Prime as output if it's a prime number.

EDIT: As you can see in the comments Neil Kandalonkar explained how the regexp by Abigail works.

EDIT 2011-04-06: I happened to stumble upon what I believe is the first time Abigail showed this to the world. It's in a post in comp.lang.perl.misc back in 1997. I also found that at http://www.cpan.org/misc/japh there's a couple more

perl -wle 'print "Prime" if (0 x shift) !~ m 0^\0?$|^(\0\0+?)\1+$0'
perl -wle 'print "Prime" if ("m" x shift) !~ m m^\m?$|^(\m\m+?)\1+$mm'

Posted in Ruby, Math | 6 comments

Comments

Comments closed

    1. Avatar
      Neil Kandalgaonkar Sat, 26 May 2007 20:43:37 GMT

      As the page makes clear, credit should go to Abigail. I merely explained it.

    2. Avatar
      Jonas Elfström Sun, 27 May 2007 22:53:36 GMT

      Sorry, now it has been corrected.

    3. Avatar
      Jonas Elfström Sun, 20 Sep 2009 21:07:14 GMT

      Seems Neils site has gone missing. Here’s another nice explanation: http://paddy3118.blogspot.com/2009/08/story-of-regexp-and-primes.html

    4. Avatar
      Jonas Elfström Mon, 18 Jan 2010 20:46:43 GMT

      https://stackoverflow.com/questions/20448/what-is-the-most-brilliant-regex-youve-ever-used/20546#20546

      And it was created by http://www.abigail.be/

    5. Avatar
      Jonas Elfström Wed, 04 Aug 2010 07:44:05 GMT

      The prime that wasn’t - explains how it works, it’s inefficiency and why PHP reported 22201 as prime.

      The Ruby implementation of RegEx differs in that aspect but I don’t know if it has a set limit or if it’s just limited to virtual memory of the machine.

      > ('1' * 222201) =~ /^1$|^(11+?)\1+$/
=> 0
> ('1' * 222199) =~ /^1$|^(11+?)\1+$/
=> nil

      222201 is not prime but 222199 is and that is what the above shows. The second expression took a couple of minutes to run.

    6. Avatar
      Jonas Elfström Thu, 12 Jan 2012 11:59:13 GMT

      Peteris Krumins explanation of how this works can be found at http://www.catonmat.net/blog/perl-regex-that-matches-prime-numbers/

RSS feed for this post

Comments are closed