For project Euler problem 3 we work on a few basic principles that we will use for several upcoming problems (yay reusable code!), factorization and determining whether a number is prime. Here is the problem:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
One way one could complete this problem would be to find all factors of the given number, and loop through checking if they are prime, returning only the largest one. To start out, let’s find all factors of a number.
import math
def findAllFactors(number):
factors = list()
for i in xrange(1, long(math.sqrt(number))):
if number%i == 0:
factors.append(i)
return factors
Here, we are simply looping through the numbers between 1 and the square root of the number, looking for numbers that divide evenly into our original number. Numbers that divide evenly are factors, so we add them to a list which we return afterward. Alternately, we could create a generator to return all factors:
import math
def findAllFactors(number):
for i in xrange(1, long(math.sqrt(number))):
if number%i == 0:
yield i
Next, we loop through each factor, checking to see if it is prime using the following code:
def isPrime(n):
n = abs(long(n))
if n < 2:
return False
if n == 2:
return True
if not n & 1:
return False
for x in range(3, long(n**0.5)+1, 2):
if n % x == 0:
return False
return True
If we have a prime factor, let’s toss it in a list for now:
if __name__ == "__main__":
factors = findAllFactors(600851475143L)
primeFactors = list()
for f in factors:
if isPrime(f):
primeFactors.append(f)
or if you are using the generator:
if __name__ == "__main__":
primeFactors = list()
for f in findAllFactors(600851475143L):
if isPrime(f):
primeFactors.append(f)
Now we simply grab the largest number in the list by sorting it and grabbbing the last item!
primeFactors.sort()
print "The Correct answer is: %d" % (primeFactors[-1])
