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.