From: Charles Zheng <snarles2@...>
Date: 2008-04-01T11:23:07+09:00
Subject: Re: Primes in P?

Michael Brooks wrote:
> Hello Charles:
>
> Here is an example of that algorithm demonstrated via a method which
> extends the Fixnum class.
> 
> class Fixnum
>    def is_prime?
>      ((("1" * self) =~ /^1$|^(11+?)\1+$/) == nil)
>    end
> end
...
> The turnaround time on solving is almost instantaneous for this
> algorithm until the numbers start gets really big (i.e. like the 123457
> above).  I don't know if this matches the criteria for "polynomial
> running time" but thought you might find this interesting if you didn't
> know about it.
> Michael

That is pretty cool. It is not of polynomial running time since it tries 
to factor the number brute-force, but that is a very nifty reg EXP 
trick.
-- 
Posted via http://www.ruby-forum.com/.