Clojure入門 - Project Eulerを解いてみる 問23
過剰数の和として表せないすべての数字の和を求める。
とりあえず問題文に出てきた、過剰数の和として表せない数字の上限(それ自体は過剰数の和として表せるけど)を定数として定義。
(def MAX-NON-ABUNDANT-SUM 28123)
問21で出てきたdivisors関数をまた使う。
(def divides? (comp zero? rem)) (defn divisors [n] (->> (range (Math/sqrt n)) (map inc) (filter #(divides? n %)) (mapcat (fn [x] [x (/ n x)])) (into (sorted-set)) drop-last))
これを使って過剰数か否かを調べる関数を作成。
(defn divisors-sum [n] (apply + (divisors n))) (defn is-abundant [n] (< n (divisors-sum n)))
上限以下のすべての過剰数を算出し、それら二つの和を集合として作成。
(def abundance (filter is-abundant (range 1 MAX-NON-ABUNDANT-SUM))) (def abundant-sums (set (for [x abundants y abundants] (+ x y))))
ここが一番重い。O(N2)になってしまっているのが嫌。
あとは、上限までの数字すべてから、その集合に含まれていないものを摘出して足し合わせるだけ。
(defn abundant-sum? [n] (contains? abundant-sums n)) (def non-abundant-sums (remove abundant-sum? (range 1 MAX-NON-ABUNDANT-SUM))) (apply + non-abundant-sums)
filterの逆のremoveをはじめて使った。(filter (complement predicate))
とどっちがいいだろうか。名前はfilter-notとかの方がわかりやすい気もする。if-notとかとも対応するし。