Project Euler Problem 087

import Data.List
import Control.Monad
import qualified Data.Set as S
limit :: Integer
limit = 50000000
nubOrd :: Ord a => [a] -> [a]
nubOrd xss = go S.empty xss where
  go s (x:xs)
   | x `S.member` s = go s xs
   | otherwise        = x : go (S.insert x s) xs
  go _ _              = []
-- p*p(1+p+p*p)と分解するより
-- p^2,p^3,p^4でとるほうが要素数が減って早い  
ans1 :: Int
ans1 = length $ nubOrd $ sort [a+b+c|
                               a<-fst$ span (< limit)$ map (join(*))primes,
                               b<-fst$ span (< limit)$ map (^(3::Integer))primes,
                               c<-fst$ span (< limit)$ map (^(4::Integer))primes,
                               a+b+c< limit]

primes :: [Integer]
primes = 2:f [3] [3,5..] where
  f (x:xs) ys = ps ++ f (xs++ps) [z | z<-qs,z`rem`x/=0] where
    (ps,qs) = span (< x*x) ys

       
--1097343  
main :: IO ()
main = print ans1