# Project Euler Problem 77 Solution

## Question

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

\displaystyle \begin{aligned} &7 + 3 \\ &5 + 5 \\ &5 + 3 + 2 \\ &3 + 3 + 2 + 2 \\ &2 + 2 + 2 + 2 + 2 \end{aligned}

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

primes :: [Int]
primes = 2 : sieve primes [3,5..] where
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
where (h, t) = span (< p*p) xs

primePartition :: Int -> Int
primePartition = p primes where
p _ 0 = 1
p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

main :: IO ()
main = print $fst$ head $dropWhile ((<= 5000) . snd) [(n, primePartition n) | n <- [1..]] $ ghc -O2 -o prime-summations prime-summations.hs
\$ time ./prime-summations
real   0m0.010s
user   0m0.008s
sys    0m0.000s