Today’s solution introduces a function we’re going to be using over and over again. Namely, generating a sequence of prime numbers. There are faster, more complicated ways to do this, but they’re not needed right now so I’m going to keep things simple.

Problem 3

Find the largest prime factor of 600851475143.

F# Solution

First things first: 600851475143 is outside the space of a 32-bit integer, so we need to make sure we use 64-bit numbers for everything.

My general plan of attack here is to generate prime numbers and test them as a factor of 600851475143. We don’t have to test all the factors. We can stop at the square root, because a number n can’t have a factor > sqrt(n).

First, how do you tell if a number is prime?

let int64sqrt (i : int64) = int64(sqrt(float i))

let isPrime64 (i : int64)  =
    if i <= 1L then false
    elif i = 2L then true
    elif (i &&& 1L) = 0L then false
    else
        let sr = int64sqrt i
        seq { 3L..2L..sr } |> Seq.forall (fun f -> i%f<>0L)

The code above tests to see if the number is 2. If it is, it’s prime. Otherwise, if it’s even, it’s not prime. Finally, it checks all odd numbers up to the square root of i to see if they divide evenly into i. If any of them do, i is not prime.

Now that we can tell if a number is prime, we can generate the next prime >= i:

let rec nextPrime64 (i : int64) =
    match i with
    | i when isPrime64 i -> i
    | i -> nextPrime64 (i + 1L)

The function above is a tail recursive function. Idiomatic F# uses functions like this a lot. Where loops are your friend in other languages, recursive functions are your friend in F#.

With those tools in hand, we can use Seq.unfold to generate a sequence of primes. This function generates all primes below the specified number.

let getPrimesBelow64 (max : int64) =
    let primeGenerator candidate =
        if candidate > max then
            None
        elif candidate = 2L then
            Some(2L,3L)
        else
            let next = nextPrime64 candidate
            if next >= max then
                None
            else
                Some(next,next+2L)

    Seq.unfold primeGenerator 2L

And finally, with all that in place, solving the problem is easy.

[<Literal>]
let target = 600851475143L

getPrimesBelow64 (int64sqrt target)
|> Seq.filter (fun x -> target % x = 0L)
|> Seq.max

We generate all primes below sqrt(600851475143) and filter out ones that are not a factor of target. Then we use Seq.max to get the answer.