#### Thursday, July 16th, 2009...21:09

## Project Euler Problems #3 and #5

I got ahead of myself last post and skipped problem 3. Maybe it’s because it wasn’t that interesting: what’s the largest prime factor of 600851475143?

Being an odd number meant 2 was not the largest prime factor, and no even numbers are prime so this simple trial division function seemed to work pretty well:

def largestPrimeFactor(num): factor = 3 while factor <= num: if num % factor == 0: num /= factor else: factor += 2 return factor iterations = 100 t = timeit.Timer("largestPrimeFactor(600851475143)", "from __main__ import largestPrimeFactor") print "Answer: %d. %d iterations took %.3f seconds" % \ (largestPrimeFactor(600851475143), iterations, \ t.repeat(1,iterations)[0])

Answer: 6857. 100 iterations took 0.949 seconds

It relies on the fact that every composite number can be represented by a unique set of prime factors. For example 8 is 2 * 2 * 2, 12 is 2 * 2 * 3, 42 is 2 * 3 * 7. This bit of knowledge proved very useful in problem #5, which asked for the first number evenly divisible by the numbers 1 - 20. For the first time, I was able to solve a problem with just pen and paper.

I started by listing the prime numbers less than 20 as each of these needed to be represented in the product: 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19. Then I filled in the blanks with the unique prime factorizations of the other numbers:

4 is 2 * 2, so now the product is: 2 * 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19

6 is 2 * 3 which is already accounted for

8 is 2 * 2 * 2, so now the product is: 2 * 2 * 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19

9 is 3 * 3, so I added another 3: 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19

10 is 2 * 5 which is already accounted for

12 is 2 * 2 * 3 which is already accounted for

14 is 2 * 7, already accounted for

15 is 3 * 5, already accounted for

16 is 2 * 2 * 2 * 2, so I add another 2: 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19

18 is 2 * 3 * 3, already accounted for

20 is 2 * 2 * 5, already accounted for

I did write a quick program to verify I was correct:

x = 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19 for d in xrange(1,21): print '%d \ %d = %d' % (x,d,(x % d))

which outputs:

232792560 \ 1 = 0

232792560 \ 2 = 0

232792560 \ 3 = 0

232792560 \ 4 = 0

232792560 \ 5 = 0

232792560 \ 6 = 0

232792560 \ 7 = 0

232792560 \ 8 = 0

232792560 \ 9 = 0

232792560 \ 10 = 0

232792560 \ 11 = 0

232792560 \ 12 = 0

232792560 \ 13 = 0

232792560 \ 14 = 0

232792560 \ 15 = 0

232792560 \ 16 = 0

232792560 \ 17 = 0

232792560 \ 18 = 0

232792560 \ 19 = 0

232792560 \ 20 = 0

## Comments are closed.