003 - prime factors

Problem 3:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 317584931803?

Things are getting tougher at this point. Exhaustive search would be foolhardy, and many of the simple algorithms use arrays that have a length that is half the size of the targeted number. (With 1/3 of a trillion possibilities, there's a reason why factorisation lies at the heart of cryptography.)

Still we might be able to get away with a simple approach: starting from 2 (the lowest factor), try to divide the larger number. If successful, reduce the larger number and repeat. Otherwise increment our divisor. This keeps memory requirements low (no arrays need be generated) and indeed we don't actually explicitly check for primes. (If our divisor is successful, it cannot have had a divisor that would have been successful.) The loop terminates either when the divisor counts up to the residue:

def prime_factors(n):
   assert (0 < n)
   if (n == 1):
      return [n]

   factors = []
   residue = n
   while True:
      if residue == 1:
         break

      c = 2
      while (residue % c):
         c += 1

      factors.append(c)
      residue /= c

   return factors

print prime_factors (317584931803L)

This code is borrowed from Wblog3 as below. It returns an answer almost instantly.