Project Euler Problem Number 3
Project Euler problem 3 reads as follows:
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
There are no special Python features here that really require explaining. The logic is also straightforward: find the smallest prime that divides evenly into "number"; reset "number" to number/prime; if prime is greater than the square root of number, you have your answer. Solution works in both Python and IronPython.
def GetNextPrime(allPrimes):
"""Given a sequential list of prime numbers, return
the next prime number
"""
value = allPrimes[-1]
if value == 2:
return 3
while True:
value += 2
for prime in allPrimes:
if value % prime == 0:
break;
else:
return value
def Euler003(number = 600851475143):
# import the square root function, seed the primes list
# and determine what
# the largest possible factor
from math import sqrt
primes = [2,3]
limit = sqrt(number)
# if the last prime number exceeds our limit, we're out
while primes[-1] <= limit:
for prime in primes:
if number == prime:
# if the prime and the number are the same,
# we've found our answer. break out of
# the loop
return number
elif number % prime == 0:
# number isn't prime! largest prime factor
# will be in number/prime.
number /= prime
limit = sqrt(number)
break
else:
# still didn't find number % prime == 0? Maybe
# we need bigger prime numbers
while primes[-1] <= limit:
# get next prime number
primes.append(GetNextPrime(primes))
# if number is divisible by next prime number
if number % primes[-1] == 0:
if number == primes[-1]:
break
number /= primes[-1]
limit = sqrt(number)
break
return number
print Euler003()