Project Euler Problem 5
問題5: 1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか[=>原文和訳]
20の階乗は float型で正確な整数を扱える範囲を超えてしまいます。ですが、今回は階乗ではなく最小公倍数なので floatや、もしかしたら integer の範囲で収まるかもしれません。ダメもとでやってみましょう。
とりあえずやってみる
(defun problem005 (N) "1〜Nの整数の最小公倍数を求める" (let ((n 0) (lis nil)) (dotimes (n N) (setq lis (cons (1+ n) lis))) (apply #'lcm lis))) (problem005 20)
1からNまでの数のリストを作って最小公倍数を求めます。Emacs Lisp には(厳密には clパッケージに)最小公倍数を求める関数 lcm が用意されていますのでこれを使えば終了です。lcm 関数は整数にしか適用できませんので、これがダメなら自作することになりそうですが。。。
実行すると幸運にも答えらしきものが得られました。あってるっぽいですね。
テストと実験
あっさりできてしまったので、テスト関数でも作って見ましょうか。
;; テスト用関数 (defun problem005-test (N ans) (let ((n 0) (result nil)) (dotimes (n N result) (let ((n (1+ n))) (setq result (cons (= (* (/ ans n) n) ans) result))))))
N の値と計算結果 ans を渡すと「割って掛けて元の値と比較」を1〜Nまで繰り返します。結果はリストにして返します。使い方は次のようにします。
(let ((N 20)) (message "%s" (problem005-test N (problem005 N)))) > "(t t t t t t t t t t t t t t t t t t t t)"
messageで出力しているので結果は Messageバッファに出力されます。すべて t なので正しい解が得られているようです。Nを増やしてみるとN=22が計算できる限界のようです。