From: Todd Benson <caduceass@...>
Date: 2008-04-01T23:15:49+09:00
Subject: Re: Primes in P?

On Tue, Apr 1, 2008 at 5:19 AM, Todd Benson <caduceass@gmail.com> wrote:
>
> 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]

Oh, btw, "n" was a bad choice of variable name here if you go by the
wikipedia article.  In their notation, you want to find the greatest
prime factor of (r-1).

Just pointing out what probably is obvious.

cheers,
Todd