James Pine Has A Blog

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