Regexp and Prime numbers

[Tim Pease]

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!

 

[Tim Pease]

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?

 

[James Edward Gray II]

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.

Wow, that was just awesome.

James Edward Gray II

 

[email55555]

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