[Project Euler] Problem 5 「最小の倍数」

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

最小公倍数を求める問題です。

1. Problem 3で作成した手続きを使って素因数分解する.
2. 1から20までの整数を素因数分解した結果から, 重複部分を取り除く.
3. その結果を掛け合わせる.

定義する手続きは次のとおりです.

(require srfi/1)

(define (square n) (* n n))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

;; 素因数分解
(define (prime-factorization n)
  (let ((a (smallest-divisor n)))
    (if (= a n)
        (list n)
        (cons a (prime-factorization (/ n a))))))

;; リストから要素を一つ取り除く
(define (remove-one lst obj)
  (cond ((null? lst) ())
        ((equal? (car lst) obj) (cdr lst))
        (else (cons (car lst) (remove-one (cdr lst) obj)))))
  
;; bの要素がaに含まれてない場合にaに追加する.
(define (merge a b)
  (cond ((null? a) b)
        ((null? b) a)
        ((member (car b) a) 
         (cons (car b) 
               (merge (remove-one a (car b)) (cdr b))))
        (else (cons (car b) (merge a (cdr b))))))

(define (my-lcm n)
  (fold *
        1
        (fold merge 
              ()
              (map prime-factorization (iota n 1)))))

計算結果は次のようになりました.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (my-lcm 10)
2520
> (my-lcm 20)
232792560
>