Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
41 lines (31 sloc) 1.31 KB
{-
- Solution to Project Euler problem 60
- Copyright (c) Project Nayuki. All rights reserved.
-
- https://www.nayuki.io/page/project-euler-solutions
- https://github.com/nayuki/Project-Euler-solutions
-}
import Data.Numbers.Primes (isPrime, primes) -- From https://hackage.haskell.org/package/primes
-- Arbitrary initial limit for the sum of the set of chosen concatenatable primes.
-- If sufficiently large then the answer will be correct; otherwise it will be -1.
initialLimit = 100000
setSize = 5
main = putStrLn (show ans)
ans = findSmallerSetSum initialLimit (-1)
findSmallerSetSum :: Int -> Int -> Int
findSmallerSetSum limit bestAns = let nextAns = (findSetSum [] limit primes) in
if nextAns /= -1 then (findSmallerSetSum (nextAns - 1) nextAns) else bestAns
findSetSum :: [Int] -> Int -> [Int] -> Int
findSetSum foundSet limit nextPrimes
| length foundSet == setSize = sum foundSet
| otherwise = findCandidate nextPrimes
where
findCandidate (p:nextPrimes)
| p > limit = -1
| ((all (isConcatPrime p) foundSet) && s /= -1) = s
| otherwise = findCandidate nextPrimes
where
s = findSetSum (p:foundSet) (limit - p) nextPrimes
isConcatPrime :: Int -> Int -> Bool
isConcatPrime x y = (isPrime $ readInt $ show x ++ show y) && (isPrime $ readInt $ show y ++ show x)
where readInt = read :: String -> Int