Regexp and Prime numbers

ruby-talk
1

This is a one-liner Ruby script that will tell you if a given number is prime.

ruby -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~
/^1$|^(11+?)\1+$/' [number]

I cannot take credit for this one -- it originally came from Perl. The
website listed below gives the full explanation of how the regexp
works.

http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

I highly recommend reading this if you want to flex your regexp muscles today.

Blessings,
TwP

ruby -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~ /^1$|^(11+?)\1+$/' 42

It may be the answer to life, the universe, and everything, but it
certainly isn't prime!

2

Now that is very interesting. Do you know if Ruby 1.9 is running
Onigurma <sp?>, the new regexp handler?

···

On 3/20/07, gga <GGarramuno@aol.com> wrote:

On Mar 19, 4:07 pm, "Tim Pease" <tim.pe...@gmail.com> wrote:
>
> ruby -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~ /^1$|^(11+?)\1+$/' 42
>

This is pretty cool. Particularly as a simple benchmark for regex
backtracking.
It highlites some of the performance issues of backtracking in ruby1.8
and 1.9.
And it also highlites issues with Perl's backtracking.

Speed issues:
> time ruby1.9 -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~ /^1$|^(11+?)\1+$/' 22441
Prime

real 0m2.111s
user 0m2.084s
sys 0m0.024s

> time perl -wle 'print "Prime" if (1 x shift) !~ /^1$|^(11+?)\1+$/' 22441
Prime

real 0m0.230s
user 0m0.208s
sys 0m0.020s

But... on larger numbers...

> ruby1.9 -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~ /^1$|^(11+?)\1+$/' 104729
Prime

> perl -wle 'print "Prime" if (1 x shift) !~ /^1$|^(11+?)\1+$/' 104729
Segmentation fault

> perl -v
This is perl, v5.8.8 built for x86_64-linux-gnu-thread-multi

3

Wow, that was just awesome.

James Edward Gray II

···

On Mar 19, 2007, at 2:07 PM, Tim Pease wrote:

This is a one-liner Ruby script that will tell you if a given number is prime.

ruby -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~
/^1$|^(11+?)\1+$/' [number]

I cannot take credit for this one -- it originally came from Perl. The
website listed below gives the full explanation of how the regexp
works.

http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

I highly recommend reading this if you want to flex your regexp muscles today.

4

Cool! I couldn't resist porting it to Java, so here is my Java version
(It is not one-liner, but maybe one statement?) :

public class PrimeTester {
  public static void main(String args) {
    System.out.println(String.format("%0" + args[0] + "d",
0).matches("^0$|^(00+?)\\1+$") ? "Not prime" : "Prime");
  }
}

http://davidtran.doublegifts.com/blog/?p=12

···

On Mar 19, 3:07 pm, "Tim Pease" <tim.pe...@gmail.com> wrote:

This is a one-liner Ruby script that will tell you if a given number isprime.

ruby -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~
/^1$|^(11+?)\1+$/' [number]

I cannot take credit for this one -- it originally came from Perl. The
website listed below gives the full explanation of how theregexp
works.

http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

I highly recommend reading this if you want to flex yourregexpmuscles today.

Blessings,
TwP

ruby -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~ /^1$|^(11+?)\1+$/' 42

It may be the answer to life, the universe, and everything, but it
certainly isn'tprime!

5

For those of us on Windows command line:

ruby -wle "puts 'Prime' unless ('1' * ARGV[0].to_i) =~ /^1$|^(11+?)\1+$/"

That's cool.

Jason

···

On 3/20/07, Tim Pease <tim.pease@gmail.com> wrote:

On 3/20/07, gga <GGarramuno@aol.com> wrote:
> On Mar 19, 4:07 pm, "Tim Pease" <tim.pe...@gmail.com> wrote:
> >
> > ruby -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~
/^1$|^(11+?)\1+$/' 42
> >
>
> This is pretty cool. Particularly as a simple benchmark for regex
> backtracking.
> It highlites some of the performance issues of backtracking in ruby1.8
> and 1.9.
> And it also highlites issues with Perl's backtracking.
>
> Speed issues:
> > time ruby1.9 -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~
/^1$|^(11+?)\1+$/' 22441
> Prime
>
> real 0m2.111s
> user 0m2.084s
> sys 0m0.024s
>
> > time perl -wle 'print "Prime" if (1 x shift) !~ /^1$|^(11+?)\1+$/'
22441
> Prime
>
> real 0m0.230s
> user 0m0.208s
> sys 0m0.020s
>
> But... on larger numbers...
>
> > ruby1.9 -wle 'puts "Prime" unless ("1" * ARGV[0].to_i) =~
/^1$|^(11+?)\1+$/' 104729
> Prime
>
> > perl -wle 'print "Prime" if (1 x shift) !~ /^1$|^(11+?)\1+$/' 104729
> Segmentation fault
>
> > perl -v
> This is perl, v5.8.8 built for x86_64-linux-gnu-thread-multi
>

Now that is very interesting. Do you know if Ruby 1.9 is running
Onigurma <sp?>, the new regexp handler?