Problem 87

http://projecteuler.net/index.php?section=problems&id=87

ナイーブな方法で解けた。遅いけど。

import Number
import Data.List
import Data.Array.IArray
import System
primesS = map (^2) primes
primesC = map (^3) primes
primesF = map (^4) primes
p087 :: Integer -> Array Integer Bool
p087 n =accumArray (||) False (1,n) [(x+y+z,True)|x<-takeWhile(<n-12)primesF,y<-takeWhile(<n-4-x)primesC,z<-takeWhile(<n-x-y)primesS]
main =getArgs>>=print.foldl1' (+).map (const 1).filter id.elems.p087.read.head

どうやら、ArrayよりSetのほうが速い

import Number
import qualified Data.Set as S
p087' n= S.fromList [x+y+z|x<-takeWhile(<n-12)primesF,y<-takeWhile(<n-4-x)primesC,z<-takeWhile(<n-x-y)primesS]
main =print.S.size.p087'$5*10^7

なんでかなー。

More Reading
Newer// Problem 86
Older// Problem 90