Approach: Keep evenly dividing the upper limit by numbers which are smaller than its square root. When further such division is impossible the result is the largest prime number which is a factor of the upper limit.
>>> from math import sqrt
>>> from math import floor
>>> upperLimit = 600851475143
>>> i = 2
>>> stoppingPoint = floor(sqrt(upperLimit))
>>> while (i < stoppingPoint):
... if (upperLimit % i == 0):
... upperLimit /= i
... stoppingPoint = floor(sqrt(upperLimit))
... else:
... i += 1
...
>>> upperLimit
6857L
>>>
Sunday, August 24, 2008
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment