７２問目

http://projecteuler.net/index.php?section=problems&id=72
d ≦ 1,000,000 について、既約分数 n/d はいくつあるか求める。
dを分母とする既約分数の数はトーティエント関数φ(d)に一致するので、それを1000000まで足し合わせています。

import Data.List

main = print $ euler072 1000000

euler072 :: Integer -> Integer
euler072 d = sum $ map phi [2..d]

phi :: Integer -> Integer
phi n = foldl (\ m d -> m - (div m d)) n $ nub $ factors primes n

factors :: [Integer] -> Integer -> [Integer]
factors (p:ps) n
    | q < p = [n]
    | r == 0 = p : factors (p:ps) q 
    | otherwise = factors ps n
    where (q, r) = divMod n p

primes :: [Integer]
primes = 2 : filter isPrime [3..]

isPrime :: Integer -> Bool
isPrime x = all ((/= 0) . mod x) $
    takeWhile (<= (floor $ sqrt $ fromIntegral x)) primes