Project Euler Problem 21

問題21: 10000未満の友愛数の合計を求めよ。[=>問題文]
　素数リスト、素因数分解、約数、メモ化と、これまでに出てきた要素がいろいろ活用できる良い問題ですね。

問題21の解答

;; Emacs Lisp
(require 'cl)
(require 'math-lib)

(defun problem021 (n)
  (let ((primes (primes-sieve (1+ (truncate (sqrt n)))))
        (memo (make-vector n -1))
        (amicable-numbers))
    (do ((m 1 (1+ m)))
        ((= m n))
      (let ((sum (- (apply #'+ (get-divisors m primes)) m)))
        (aset memo m sum)
        (when (and (< sum n)
                   (not (= sum m))
                   (= (aref memo sum) m))
          (push m amicable-numbers)
          (push sum amicable-numbers))))
    (apply #'+ amicable-numbers)))

(problem021 10000)

　素数列挙等のライブラリを改めてまとめた math-lib ファイルを作りました。素数リストを必要とする関数は引数に素数リスト (primes)をとるようにしています。必要な素数の上限がわかる問題なので素数リストは、エラトステネスのふるい (primes-sieve) で作っています。
　整数 m の真の約数の和を memo のインデックス m 番目に保存して、友愛数チェックを行っています。

約数リスト作成関数

　今回作った約数リスト作成関数です。

(defun get-divisors (n primes)
  "約数リスト作成"
  (let ((factors (factorize n primes))
        (dest))
    (labels
        ((repeat (lis acc)
                 (if (null lis)
                     (push acc dest)
                   (destructuring-bind (n . count) (car lis)
                     (do ((i 0 (1+ i)))
                         ((< count i))
                       (repeat (cdr lis) acc)
                       (setq acc (* acc n)))))))
      (repeat factors 1))
    dest))

　素因数分解した後、順列を作る要領で再帰関数 repeat で約数を順次作成しています。作成される約数リストはソートされていません。また n 自身もリストに含まれます（真の約数リストではない）。
　前掲の problem021 では、この get-divisors の作成したリストの要素の和をとった後、対象の数自身を引くことで「真の約数の和」を得ています。