Project Euler の Problem 5 (日本語訳)がおもしろそうだったのでやっていました。
まずは正攻法
problem5_0.rb
n=20
1.upto(Float::INFINITY).find{|i| (1..n).all?{|j| i % j ==0}}
なかなか答えが出ません...
少なくともnの倍数のはずですので、nの倍数だけをチェック、
大きい数字の倍数の方が少ないので、n-1から小さい方にチェックしていくように変更しました。
problem5_1.rb
n=20
n.step(Float::INFINITY, n).find{|i| (n-1).downto(2).all?{|j| i % j ==0}}
これでやっと17秒です。
Haskellで
problem5_1.hs
import Data.List
n=20 :: Int
lcm1= find (\i -> all (\j -> mod i j ==0) [n-1, n-2..2]) [n, n*2..]
main = print lcm1
これで0.5秒程度です。
クイズっぽくなって恐縮ですが、(書かれる方の主観で結構ですので)簡単なアルゴリズムで速度がでる方法のコメントをお願いします。
アルゴリズムですので言語は問いません。
nが10以上で、上限は計算が64ビット符合付き整数で処理できるところまでということでお願いします。
追記(2017.6.12)
みなさんコメントありがとうございました。
コメントをまとめますと、「最小公倍数」を求めれば良いということです。
Ruby
2.upto(n).inject(&:lcm)
Haskell
problem005 n = foldr1 lcm [2..n]