Problem 57
http://projecteuler.net/index.php?section=problems&id=57
時間がかかるのは桁数のカウント。
num_digits 0 = 0 num_digits n = 1 + (num_digits (div n 10)) a = take 1000 ((1,1):[ (p + q * 2, p + q) | (p, q) <- a ]) main = print (length (filter (\(p,q) -> (num_digits p) > (num_digits q)) a))
割り算より掛け算を使うほうが速い。
num_digits n = length (takeWhile (<= n) a) where a = 1:(map (*10) a) a = take 1000 ((1,1):[ (p + q * 2, p + q) | (p, q) <- a ]) main = print (length (filter (\(p,q) -> (num_digits p) > (num_digits q)) a))
本当はもっと速い方法があるがパス。
Problem 58
http://projecteuler.net/index.php?section=problems&id=58
スパイラルの対角線上の数列が、1から始まって差分が
2,2,2,2,4,4,4,4,6,6,6,6,...
となることを利用する。
is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3..]) is_prime2 n = if is_prime n then 1 else 0 d = 2:2:2:2:[ n + 2 | n <- d ] -- diff a = 1:[ m + n | (m, n) <- zip a d ] -- series on diagonal r = (1,0):[ (m + 1, (is_prime2 l) + n) | (l, (m, n)) <- zip (tail a) r ] b = head (filter (\(m, n) -> mod m 4 == 1 && m > n * 10) (tail r)) main = print((div (fst b) 4) * 2 + 1)
