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.

Other Posts in This Series