The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

One way to find the prime factors is to make a function that starts at two, tests to see if it's a factor, and iterate upwards. Then, when a factor is found, save it and use recursion to call the function with the number divided by the factor as the argument.

For example, let's say we want to find the prime factors of 100. We have our function, foo(n) with n = 100, that starts at 2, iterates up, and stops when a factor of 100 is found. Since 2 divides into 100, it stops at the first iteration, saves 2, and calls foo(100/2). We can do this because there can't be any factors above 50, so we won't bother checking them, which vastly increases our efficiency. Proceeding through foo, it returns the numbers 2, 2, 5, 5. The largest number of the results is the answer.

In Common Lisp:

(defun problem-3 ()
 (reduce #'max
     (labels ((prime-factors (num)
                (unless (<= num 1)
                  (do ((x 2 (1+ x)))
                        ((zerop (mod num x))
                         (cons x
                                  (prime-factors (/ num x))))))))
       (prime-factors 600851475143))))

The above lisp code can be cryptic for people unfamiliar with the language. Think of labels as just defining the local function prime-factors. Prime-factors takes a number, tests to see if it's greater than one, then if it is proceeds into the do-loop. The do-loop starts with x = 2 and increases x by 1 with every iteration. It stops when the remainder of num / x = 0. When it stops, it outputs a list of x and the result of prime-factors (num / x). This recursions stops when the number = 1. The reduce #'max statement finds the maximum value of the list returned by prime-factors.


In Python:

def flatten(L):
    if type(L) != type([]): return [L]
    if L == []: return L
    return flatten(L[0]) + flatten(L[1:])

def primeFactors(num):
    if num <= 1:
        return []
    x = 2
    while x <= num:
        if num % x == 0:
            return [x] + [primeFactors(num / x)]
        x += 1

def problem3():
    return max(flatten(primeFactors(600851475143)))