Project Euler 解答

Project Euler Problem 072

Project Euler Problem 072

import Data.List

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
factor :: Integer -> [Integer]
factor nn = factorimpl nn primes where
  factorimpl n pri@(p:xs) =
    if p*p>n then [n]
    else if n`rem` p == 0 then
      p:factorimpl (n `quot` p) pri
         else
           factorimpl n xs
tot :: Integer -> Integer
tot 0 = 0
tot 1 = 1
tot n = foldl' (\a l@(x:_) -> a*(x^(length l) - x^(length l-1))) 1 $ group $ factor n
fn :: Integer -> Integer
fn n = 1  + (sum $ map tot [1..n]) - 2 -- -2するのは、0/1と1/1が含まれてないから
ans1 :: Integer
ans1 = fn (10^(6::Integer))


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

since 2013