http://projecteuler.net/index.php?section=problems&id=70
pが大きい方から、素数の組(p, q) (p ≤ q)に対し、調べていく。
import Data.List is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3,5..]) digits 0 = [] digits n = (digits (div n 10)) ++ [ mod n 10 ] normalize n = (sort . digits) n is_perm (m,n) = (normalize m) == (normalize n) phi (p, q) = if p == q then p * (p - 1) else (p - 1) * (q - 1) limit = 10^7 pairs = reverse (takeWhile (\(p,ps) -> p * p < limit) a) where a = (2, primes):[ (head ps, ps) | ps <- map (tail . snd) a ] calc_min [] m = m calc_min ((p,ps):xs) (mp,mq) | mq * p > mp * (p - 1) = (mp,mq) | otherwise = calc_min xs min_f where min_f = foldr less (mp,mq) a a = filter is_perm [ (p * q, phi (p,q)) | q <- qs ] qs = takeWhile (\q -> p * q < limit) ps less (a,b) (c,d) = if a * d < b * c then (a,b) else (c,d) main = print (fst (calc_min pairs (6,2)))
