# Project Euler – Problem 77 Solution

Presently sponsored by Serverless Guru: Your guide to cloud excellence, helping you every step of your serverless journey, including team training, pattern development, mass service migrations, architecting, and developing new solutions. Speak to a Guru today.

#### Problem

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3

5 + 5

5 + 3 + 2

3 + 3 + 2 + 2

2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

#### Solution

```// generate all prime numbers under <= this max
let max = 1000

// only check the prime numbers which are <= the square root of the number n
let hasDivisor n =
|> Seq.takeWhile (fun n' -> n' <= int(sqrt(double(n))))
|> Seq.exists (fun n' -> n % n' = 0)

// only check odd numbers <= max
let potentialPrimes = Seq.unfold (fun n -> if n > max then None else Some(n, n+2)) 3

// populate the prime numbers list
for n in potentialPrimes do if not(hasDivisor n) then primeNumbers <- primeNumbers @ &#91;n&#93;
let isPrime n = if n = 1 then false else not(hasDivisor(n))

// implement the coin change algorithm
let rec count n m (coins:int list) =
if n = 0 then 1
else if n < 0 then 0
else if (m <= 0 && n >= 1) then 0
else (count n (m-1) coins) + (count (n-coins.[m-1]) m coins)