Project Euler (Problem ID 11..15)

ID 11から15まで。

関数primes、factorとprimeFactorsは、ID 3の使い回し。

ID 11のコードをうまく書けず、汚くなってしまった…

ID 12では、素因数分解してから、また積をとっているのが良くない気がする。
素因数分解したときの指数だけ見れば良いのかな?

ID 11..15

import List

primes = [2] ++ sieve [3,5..]
	where sieve (p:ns) = [p] ++ (sieve $ filter (\n -> rem n p /= 0) ns)

factor 1 _ = []
factor m (n:ns)
	| rem m n == 0 = (n:factor (quot m n) (n:ns))
	| otherwise = factor m ns

primeFactors n = factor n primes

rtail n l
	| n == 0 = head l
	| otherwise = rtail (n - 1) $ tail l
	
prog011 = last $ sort $ ((prods prodH4) ++ (prods prodV4) ++ (prods prodDrd4) ++ (prods prodDru4))
	where
		at c r = rtail r $ rtail c $ the20x20grid
		prodH4 c r = product $ map (at c) $ [r..(r+3)]
		prodV4 c r = product $ map (\col -> at col r) $ [c..(c+3)]
		prodDrd4 c r = product $ map (\i -> at (c+i) (r+i)) $ [0..3]
		prodDru4 c r = product $ map (\i -> at (c+i) (r+3-i)) $ [0..3]
		prods p = [p c r | c <- [0..16], r <- [0..16]]

combinations (x:xs) n
	| n == 0 = [[]]
	| n == length (x:xs) = [(x:xs)]
	| otherwise = [(x:cs) | cs <- combinations xs (n - 1)] ++ (combinations xs n)

triangleNum n = sum $ [1..n]
factors n
	| n == 1 = [1]
	| otherwise = uniq $ sort $ (++) [1] $ map product [cs |
		m <- [1..length ps],
		cs <- combinations ps m]
			where ps = primeFactors n

prog012 = head $ dropWhile (\z -> snd z < 500) zipped
	where
		tNums = map triangleNum [1..]
		zipped = zip tNums (map (length . factors) tNums)

prog013 = take 10 $ show theSum
	where theSum = 
		37107287533902102798797998220837590246510135740250 +
		46376937677490009712648124896970078050417018260538 +
		-- 中略
		20849603980134001723930671666823555245252804609722 +
		53503534226472524250874054075591789781264330331690

collatzs n
	| n == 1 = [1]
	| otherwise = n:(collatzs (collatz n))
		where collatz n
			| even n = div n 2
			| otherwise = (3 * n) + 1

prog014 = last $ sort $ zip (map (length . collatzs) sNums) sNums
	where sNums = [1..(1000 * 1000 - 1)]

prog015 = div (product [21..40]) (product [1..20])

main = putStrLn $ show $ prog015