Sunday, August 24, 2008

Project Euler #3: Find largest prime factor

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
>>>

No comments: