Clojure入門 - Project Eulerを解いてみる 問２１

第二十一問

１００００未満の友愛数の和を求める。

まずは単純な解決法を試す。

ヘルパー関数：

(defn divides? [x n]
  (zero? (rem x n)))

次が「単純」なところ。除数のリストを算出する。

(defn divisors [n]
  (->> n
       (range 1)
       (filter #(divides? n %))))

バカ正直に1~n-1のすべての整数を試す方式。

あとは友愛数の定義に従ってコードを記述していくだけ。

(defn divisors-sum [n]
  (apply + (divisors n)))

(defn amicable [n]
  (and
    (= n (divisors-sum (divisors-sum n)))
    (not= n (divisors-sum n))))

(defn amicables [n]
  (->> n
       (range)
       (map inc)
       (filter amicable)))

(apply + (amicables 10000))

数秒で終わるので、Project Eulerのリミット自体には合致しているのだが。こんなに簡単な問題で数秒かかるのは癪。

divisors関数がもうちょっとなんとかなりそう。

試行錯誤してあまりうまくいかなかったのでググっていたらロゼッタコードに良さそうなアルゴリズムが載っていた。

それを個人的な好みと今回の必要に応じていじっていたら以下の通りになった。

(defn divisors [n]
  (->> (range (Math/sqrt n))
       (map inc)
       (filter #(divides? n %))
       (mapcat (fn [x] [x (/ n x)]))
       (into (sorted-set))
       drop-last))

これで私のノートパソコンでは300msecくらい。平方根まで調べて、その対となる数字は除法で計算する、という発想は自分でもあったのだが、mapcatとinto sorted-setを使うことは思いつかず、効率がさほど向上しなかった。

簡潔に記述する方法と、効率的に記述する方法と、読みやすく記述する方法と、すべて未だにわからない。とりあえず、今はthread macroを多用していて、こうする方が論理が明快なように感じるが（ロゼッタコードからのアルゴリズムもthread lastで書き直している）、これも慣れていくと変わるのだろうか。