problem 5

project euler 問題 5 です。

1 から 20 の全ての数で割りきれる最少の数を求める問題。

アルゴリズム自体は難しくないのですが、考えたロジックを scheme で表現するのに骨が折れました。素因数分解のロジックは先の問題でも使えるでしょうか。素因数分解の結果を alist で保持していますが、素因数の数が多くなってくるとこれもハッシュにした方がいいのかもしれません。

(use srfi-1)

;; alist から car が key の pair を見つけだし cdr に delta を加える。
(define (alist-plus! key delta alist)
  (let1 pair (assoc key alist)
        (if pair
          (set-cdr! pair (+ (cdr pair) delta))
          (set! alist (acons key delta alist))))
  alist)

;; alist1 へ alist2 を組み入れる key が同じ pair は cdr の大きい方を採用する。
(define (alist-max! alist1 alist2)
  (if (eq? alist2 '())
    alist1
    (let* ((key (caar alist2))
           (value (cdar alist2))
           (pair1 (assoc key alist1)))
      (if pair1
        (set-cdr! pair1 (max value (cdr pair1)))
        (set! alist1 (acons key value alist1)))
      (alist-max! alist1 (cdr alist2)))))

;; 素因数分解。例えば n が 12 だと ((2 . 2) (3 . 1)) をハッシュ table に put する。
(define (prime-factorization table n)
  (let loop ((i 2))
    (if (= (modulo n i) 0)
      (hash-table-put! table n
                       (alist-plus! i 1 (alist-copy (hash-table-get table (/ n i) '() ))))
      (loop (+ i 1)))))

;; main
(define (p5)
  (let1 table (make-hash-table)
        ;; 1 から 20 を素因数分解して
        (let loop ((i 2))
          (when (<= i 20)
            (prime-factorization table i)
            (loop (+ i 1))))
        ;; 素因数分解の結果から各素因数の一番大きい指数を調べ、その指数でべき乗し、それらを掛け合わせる
        (fold (lambda (x y) (* (expt (car x) (cdr x)) y)) 1
              (hash-table-fold table (lambda (k v r) (alist-max! r v)) '() ))))

(print (p5))