06.02.08
Project Euler: Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
A solution:
We can use the factorize function written for Problem 5, but it needs to be modified. The number to be factored is so large that the upper limit of numbers that need to be checked as factors is of type long, rather than of type int. The range() function doesn’t like numbers that large (unsurprisingly, as that would be a very very very long list to store), so a while loop needs to be used instead of a for loop.
def factorize(num):
powers = []
limit = (num/2)+1
i = 2
while i <= limit:
while num % i == 0: # ie, i is a factor of num
powers.append(i)
num = num/i
i += 1
if num == 1: break # ie, all factors have been found
if len(powers) == 0: powers.append(num) # num is prime
return powers
This function can then be used to find the prime factors of the given number.
There are ways this method can be improved: if the factor 2 is handled separately before the while loop, then the loop only needs to be done for odd numbers, using half of the iterations. As well, a separate function that tests for primality could be called at the beginning: since a prime test only needs to check up to sqrt(number) instead of number/2, it can be a lot faster to know if the number itself is prime, rather than trying to find all of its factors.
05.29.08
Project Euler: Problem 5
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
A solution:
from math import ceil
def factorize(num):
powers = []
limit = int(ceil(float(num)/2)) # we only need to look up to num/2 for factors
for i in range(2, limit+1):
while num % i == 0: # ie, if i is a factor of num
powers.append(i)
num = num/i # take factor out of num and continue with smaller num
if len(powers) == 0: # haven't found any factors, ie, num is prime
powers.append(num)
return powers
topnum = 20
master_factors = []
total = 1
for i in range(2,topnum+1):
current_factors = factorize(i)
while len(current_factors) != 0:
fact = current_factors[0]
count_difference = current_factors.count(fact)-master_factors.count(fact)
if count_difference > 0:
for j in range(count_difference): master_factors.append(fact)
del current_factors[0:current_factors.count(fact)]
for i in range(len(master_factors)): total *= master_factors[i]
print total
This code seems pretty messy, there’s surely better ways to write it. For sure, the factorize function should be changed so that it only checks odd numbers (after two), that would get rid of half the iterations. After solving the problem I looked through the forum for ways others were solving it, and found this one written in Python, from user tenigmanogo:
def gcd(a, b): while b != 0: a, b = b, a % b return a def lcm(a, b): return a*b/gcd(a, b) print reduce(lcm, range(1, 20+1))
Definitely makes me want to learn more, and get better about looking at problems in different ways. It’s so simple! Though, with the longer solution, I now have a function that will find the prime factors of a number, which will come in handy for future problems.
