Python Optimization

[Steve Howell]

On Feb 14, 11:52 am, Mark Dickinson <dicki... at gmail.com> wrote:
> On Feb 14, 4:53 pm, mukesh tiwari <mukeshtiwari.ii... at gmail.com>
> wrote:
>
> > Hello everyone. I am new to python and previously i did programming in
> > c/c++.Could some one please help me to improve the run time for this
> > python program as i don't have idea how to optimized this code.This
> > code also seems to be more unpythonic so how to make it look like more
> > pythonic . I am trying for this problem(https://www.spoj.pl/problems/
> > FACT1/).
> > Thank you
>
> One other thing:  in the 'brent' function, you're setting m to
> randrange(1, n).  What's the purpose of this?  It looks to me as
> though m controls the number of Pollard-Rho iterations that are
> clumped together at one time (before doing a gcd operation), and using
> a random number for this doesn't make a lot of sense to me.
>

The randomness also makes the algorithm a little buggy.

I tried this input:

37^5 41^5

Usually I get the right answer.  Other times I get this:

37^5 41^3 1681^1

And occasionally it appears to get into an infinite loop, which
definitely could be a cause of "slowness." :)