4つの素数の和

Haskell 30分プログラム

30分プログラム、その140。4つの素数の和

与えられた整数 N （N<=10000000）に対し、Nを４つの素数の和で表せというもの。もしNは４つの素数の和で表現できなければ、"Impossible."で答えろという。 また、４つの素数について、条件は一切なく、好きな組み合わせで良いという。

いったんSchemeでugly numberに挑んでやぶれているので、簡単なやつで。

使い方

fourPrimes 24
Just (2,2,3,17)

*Main> fourPrimes 10
Just (2,2,3,3)

*Main> fourPrimes 1
Nothing

ソースコード

import Control.Monad.List

sieve (p:ps) = p : sieve [q | q <- ps, q `mod` p /= 0]
primes = sieve [2..]

maybeHead []    = Nothing
maybeHead (x:_) = Just x

fourPrimes n = 
    maybeHead $  do a <- primes'
                    b <- primes'
                    c <- primes'
                    d <- primes'
                    guard $ a + b + c + d == n
                    return (a,b,c,d)
    where primes' = fst $ break (> n) primes

参考