Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

訳

2520は，1から10までのそれぞれの数で割り切れる最小の数である．
では，1から20までのそれぞれの数で割り切れる最小の数は何か

1から20までの自然数をすべて掛け算して素因数分解します．その中にでてくる素因数に「適当な指数」をつけて，ぞれを全部掛け合わせれば答えになります．その「適当な指数」はが20を超えない最大のものになるように定めます．

このように定めた数は，1から20までのすべての数の約数を約数としてもつのは明らかです（すなわち，1から20までのすべての数で割り切れます）．また，これより小さい数ではこのような数はありません．素因数の指数を小さくすると，割り切れない数が出てきてしまうからです．

[Haskell] そのまま実装

{-
e5.hs Project Euler Problem 5
-}

import Data.List

{-
Problem 3から素因数分解をもってくる
-}
primes::[Integer]
{-
primes=2:(eratos [3,5..])
    where eratos (p:ps) = p: (eratos [ x | x<-ps, x `mod` p /= 0 ])
-}
primes=2:3:([6,12..] >>= (\x->[x-1,x+1]))

min_fact::Integer->Integer
min_fact n = head $ filter (\x -> (n `mod` x ==0)) primes

factorization::Integer->[Integer]
factorization n 
        | n == p = [n]
        | otherwise = p :  factorization(n `div` p)
    where p = min_fact n

{-
g::Integer -> [Integer]  -> Integer
-}

f:: Integer -> Integer -> Integer
f a b = product $ map (\x -> g b x) ((group.factorization.product) [a..b])
    where g n (p:ps) = maximum [ p^i | i <- [1..((length ps)+1)], p^i <= n ]

結果．

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.6.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Prelude> :l e5.hs
[1 of 1] Compiling Main             ( e5.hs, interpreted )
Ok, modules loaded: Main.
*Main> f 1 20
232792560
*Main> f 1 10
2520
*Main> 

関数groupで素因数分解の同じ素因数を一個のリストにして長さが指数を表すようにして，これで「与えられた値以下になる累乗」を計算させています．