problem 21 - mtsuyuguの日記

project euler 問題 21 は 10000 以下の友愛数の和を求める問題です。

友愛数というのは 2 つの自然数の自分自身以外の約数の和が互いに他方と等しくなるような 2 つの自然数のことです。

6 のように約数の和が下の数と等しくなるようなモノは友愛数とは言わないみたいです。

ということで、以下のプログラムとなりました。どれだけの効果があるかは分かりませんが、一度求めた約数の和はハッシュで保持するようにしています。

;; ex.) 12 --> (6 4 3 2 1)
(define (find-divisors n)
  (let loop ((i 2)
             (result '(1)))
    (if (> i (/ n 2)) result
      (loop (+ i 1)
            (if (= (modulo n i) 0) (cons i result) result)))))

(define (p21)
  (define ht (make-hash-table))
  (let loop ((i 1)
             (result 0))
    (let* ((di (hash-table-get ht i (fold + 0 (find-divisors i))))
           (ddi (hash-table-get ht di (fold + 0 (find-divisors di)))))
      (hash-table-put! ht i di)
      (hash-table-put! ht di ddi)
      (if (> i 10000) result
        (loop (+ i 1)
              (+ result (if (and (= ddi i) (not (= i di)))
                          i 0)))))))

(print (p21))