http://projecteuler.net/index.php?section=problems&id=85
Pythonで解いたときと違う方法を採った。2000000, 1999999, 2000001, ...という数に対して三角数の積になっていないか調べる。
primes = 2:3:5:7:[ p + 6 | p <- tail (tail primes) ] calc_exp n p | mod n p /= 0 = (n, 0) | otherwise = (m, e + 1) where (m, e) = calc_exp (div n p) p factorize 1 ps = [] factorize n (p:ps) | e > 0 = (p,e):(factorize m ps) | otherwise = factorize m ps where (m, e) = calc_exp n p fact n = factorize n primes value_f f = foldr (\(p,e) y -> p^e * y) 1 f divisors [] = [([], [])] divisors ((p,e):fs) = [ (neg ((p,e1):a),neg ((p,e-e1):b)) | e1 <- [0..e], (a,b) <- divisors fs ] neg [] = [] neg ((p,e):a) = if e == 0 then neg a else (p,e):(neg a) divs n = [ (value_f f1, value_f f2) | (f1, f2) <- divisors (fact n) ] int_sqrt n = floor (sqrt (fromIntegral n)) is_square n = m * m == n where m = int_sqrt n is_valid p q = is_square (1 + p * 8) && is_square(1 + q * 8) edge n = div (-1 + (int_sqrt (1 + 8 * n))) 2 area ns = [ (edge p) * (edge q) | n <- ns, (p,q) <- divs n, is_valid p q ] n0 = 2 * 10^6 ns = n0:(n0-1):[ if n < n0 then n - 1 else n + 1 | n <- ns ] main = print (head (area ns))
