Project Euler problem three is first of *many* to deal with prime numbers.

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

What is the largest prime factor of the number 600851475143?

Eventually, we'll need a prime number generator to solve some of the more advanced problems, but this problem can be solved efficiently without one. The number in question is small enough (just 12 digits) that the divide-and-conquer method that many of us learned in elementary school will suffice.

Consider how we might use this process to find the prime factors of 140.

140 | Is 140 evenly divisible by 2? Yes! Remember 2 and divide 140 by 2. |

2 * 70 | Is 70 evenly divisible by 2? Yes! Remember 2 and divide 70 by 2. |

2 * 2 * 35 | Is 35 evenly divisible by 2? No, how about 3? No. 4? Nope. 5? Yes! Remember 5 and divide 35 by 5. |

2 * 2 * 5 * 7 | And we're done! |

This method isn't rocket science, but it gets the job done. In fact, it's pretty fast for reasonably small numbers. After all, we're not trying to find the factors of RSA-200.

The basic algorithm is pictured as a flowchart below.

The following F# function implements our algorithm.

let inline isFactor n d = n % d = 0L

let rec nextFactor n d =

let x = if d = 2L then 3L else d+2L

if isFactor n x then x else nextFactor n x

let rec findFactors n d acc =

if isFactor n d then

findFactors (n/d) d (d::acc)

elif n > d then

findFactors n (nextFactor n d) acc

else

acc

findFactors n 2L [] |> List.rev

To the uninitiated, that function might look pretty complex. In reality, it's extremely simple, but three other functions are nested inside of it. Let's look at each nested function in turn.

There's nothing tricky about isFactor. It simply abstracts the modulo operation that determines whether n is evenly divisible by d.

let x = if d = 2L then 3L else d+2L

if isFactor n x then x else nextFactor n x

nextFactor recursively determines the next value of d to be used in the algorithm. There is a small optimization here: nextFactor only produces odd numbers. Since 2 is the only even prime, why bother checking any other evens?

if isFactor n d then

findFactors (n/d) d (d::acc)

elif n > d then

findFactors n (nextFactor n d) acc

else

acc

The meat of the algorithm is handled by findFactors. Any factors found are cons'd up with the accumulator variable, acc. Note that both findFactors and nextFactor are written tail-recursively, so they can be optimized by the compiler to conserve stack space.

The *real* body of primeFactors kicks off the recursion:

The result of findFactors is passed to List.rev to return the prime factors in a more logical order (smallest to largest).

A simple test in the F# Interactive Environment shows that primeFactors works as expected.

val it : int64 list = [2L; 2L; 5L; 7L]

Almost done.

Project Euler Problem Three asks, "What is the largest prime factor of the number 600851475143?" That's just a matter of folding the list of prime factors with the max function (from the F# libraries) to get the answer.

We can generalize the folding logic above with a new function...

...And now we can write the following solution.

That's just lovely.

**NeRd Note**