Project Euler 72

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

エラトステネスのふるいがなぜこんなに遅いのか。

import Data.Array

make_primes n = filter (a!) [2..n] where
    a = sieve (array (2, n) [ (k, True) | k <- [2..n] ]) 2
    sieve a p | a!p = sieve (a // [ (m, False) | m <- b, a!m ]) (p + 1)
              | p * p > n = a
              | otherwise  = sieve a (p + 1) where
                    b = if p == 2 then [p*2,p*3..n] else [p*3,p*5..n]

sum_phi n [] = 1
sum_phi n (p:ps)
        | n < p     = 1
        | otherwise = (sum_phi n ps) +
            sum([ phi * (sum_phi (div n pow) ps) | (phi, pow) <- a ]) where
                a = takeWhile (\(_,pow) -> pow <= n) b
                b = (p-1,p):[ (x * p, y * p) | (x, y) <- b ]

limit = 10^6
primes = make_primes limit
main = print ((sum_phi limit primes) - 1)