Project Euler No. 5

Problem

$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 positive number that is evenly divisible by all of the numbers from $1$ to $20$?

Code in Haskell

Euler_005.hs

module Main where

-- ユークリッドの互除法そのまま （追記　←　大嘘）
greatestCD a 0 = a
greatestCD a b
  | a>=b = greatestCD b (a - b)
  | a<b  = greatestCD b (b - a)

{- 
　コメント欄で教えていただきました。
　こっちが本来の「ユークリッドの互除法」で
これなら計算も一瞬で終わります……実に（私の頭が）ひどい。

greatestCD m 0 = m
greatestCD m n = greatestCD n (mod m n)

-}


-- LCMは積をGCDで除したもの
leastCM a b = a*b `div` (greatCD a b)
leastCMofALL as = foldl leastCM 1 as

main = print answer
  where answer = leastCMofALL [1..20]

これは予想通り恐ろしく遅い。$1$から$20$ならなんとかなるが、$1$から$30$までにしてみると、もうまったく終わらない。

追記　上のコード内のコメントにある通りで、「ユークリッドの互除法」は悪くない。残念なのは私でした。きちんとしたヴァージョンだと爆速で終わるので、下記のものはまったく余計な代物です。でも恥の証として残しておく。

そこで、$1$から$n$までを素因数分解して、各素因数ごとに指数の最大値を取って合成するという方策を取ってみた（その方策を実行する仕方がダサいのは私が情弱だからである）。素因数分解はProblem No. 3のものを転用する：

Euler_005bis.hs

module Main where
import Control.Applicative
import Data.List
import Data.Ord (comparing)
import System.Environment (getArgs)

factoring n fs (x:xs)
  | n == 1 = fs
  | (mod n x == 0) = factoring (div n x) (x:fs) (x:xs)
  |otherwise = factoring n fs xs

factors n = group $ factoring n [] [2..n]
factorset n =  sortBy (comparing length) $ concat $ map factors [2..n]

reduce [] = []
reduce (x:xs)
  | or $ map (isPrefixOf x) xs = reduce xs
  |otherwise = x: reduce xs

build [] = 1
build (x:xs) = ((head x)^(length x)) * build xs

solve = build . reduce . factorset

-- コマンドライン引数で正整数を取って結果を返す
main =  solve<$>read<$>(!!0)<$>getArgs >>= print

明らかにムダがあるはずなのだが、それでもこれは見事に早かった。

Answer

2*******0

Comments

ちなみに$1$から$30$までだと$2329089562800$である。

MEMO

mainがコマンドライン引数を取るときにはghciではmainではなく:mainを使うこと（情弱なので初めて知った）。