On Mon, Mar 8, 2010 at 2:15 AM, Fahad Ahmad <miracles...@hotmail.com> wrote:
> Thanks Geremy,
>
> That has been an absolute bump........... GOD i cant sit on my chair, it has
> worked even on 512 bit number and with no time..........
> superb i would say.
>
> lastly, i am using the code below to calculate Largest Prime factor of a
> number:
>
> print
> ('''==============================================================================='''
> ''' CALCULATE HIGHEST PRIME
> FACTOR '''
>
> '''===============================================================================''')
>
> #!/usr/bin/env python
> def highest_prime_factor(n):
> if isprime(n):
> return n
> for x in xrange(2,n ** 0.5 + 1):
> if not n % x:
> return highest_prime_factor(n/x)
> def isprime(n):
> for x in xrange(2,n ** 0.5 + 1):
> if not n % x:
> return False
> return True
> if __name__ == "__main__":
> import time
> start = time.time()
> print highest_prime_factor(1238162376372637826)
> print time.time() - start
>
> the code works with a bit of delay on the number : "1238162376372637826" but
> extending it to
> (109026109913291424366305511581086089650628117463925776754560048454991130443047109026109913291424366305511581086089650628117463925776754560048454991130443047)
> makes python go crazy. Is there any way just like above, i can have it
> calculated it in no time.
>
>
> thanks for the support.
If you're just looking for the largest prime factor I would suggest using
a fermat factorization attack. In the example you gave, it returns
nearly immediately.
Geremy Condra
--
http://mail.python.org/mailman/listinfo/python-list
