Problem 5の回答例を読む

ログインして問題を解かないと回答例がオープンしないのが残念だ。


Problem 5 - PukiWiki

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。

では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。


10で見てみると2〜10まで素因数分解してみて、

2 3 4 5 6 7 8 9 10
------------------
2 3 2 5 2 7 2 3 2
    2   3   2 3 5
            2


共通するものを除外すると、

2 * 3 * 2 * 5 * 7 * 2 * 3 = 2520

僕は2から順番に見て行って割り切れたら割る。という方法を取ってみた。Problem 5 - ボクノス


もうちょっと式をまとめる。


2 ^ 3 * 3 ^ 2 * 5 * 7 = 2520


じっと表を見る。

2 3 4 5 6 7 8 9 10
------------------
      5   7 2 3  
            2 3  
            2

これだけわかればいい。


素数p ^ k <= 10で最大の整数k。言い換えると、floor(log(10) / log(p)) = k


1 から n までの整数全てで割り切れる最小の値は、n以下の素数リスト{p}に対して、

Πp_i^floor(log(n) / log(p_i))

となる。


スゲー感動した。


修正。

(define (problem5 n)
  (fold
    (lambda (p acc)
      (* (expt p (inexact->exact (floor (/ (log n) (log p)))))
         acc))
    1
    (filter prime? (iota n 1))))

(problem5 10) ; 2520
(problem5 20) ; 232792560

あらかじめ素数を求めておく必要があるので、速度はどうなのかわからない。要検討。