From: Todd Benson <caduceass@...>
Date: 2008-04-01T19:19:35+09:00
Subject: Re: Primes in P?

On Mon, Mar 31, 2008 at 9:23 PM, Charles Zheng <snarles2@gmail.com> wrote:
> 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.

Charles, take a peak at the mathn library for your greatest prime factor...

require 'mathn'
n = 12345654321
p n.prime_division.last[0]

hth a little,
Todd