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

第十問

200万以下の素数の和。

以下ネタバレ

(println
  (reduce +
    (take-while #(< % 2000000)
      primes)))

以上。

と言いたいところだが、ここまでくると素数作成関数の遅さが露呈してくる。正しい答えは算出されるのだが、いかんせん遅い。

エラトステネスのお出ましか？とも考えたが、まずはそもそも今作ったものが早いのかどうか確認。

(defn naive-test [n]
  (every? (fn [x] (not= 0 (mod n x)))
    (range 2 n)))

(defn prime-test [n]
  (every? (fn [x] (not= 0 (mod n x)))
    (range 2 (inc (Math/sqrt n)))))


(defn primes-with-test [test]
  (concat '(2)
    (filter test
      (map #(+ 3 (* 2 %)) (range)))))

このような単純なコードと比較してみると、素数性をテストするのに1~nまですべての数字を試すnaive-testよりはかなりはやいものの、1~n^0.5のみを試すprime-testには200万以下の素数列挙でかなり差をつけられる。

多分vectorの作成あたりで非常に重い処理になっているのではないだろうか。というわけで、ここら辺で一旦Project Eulerから移って基礎データ構造などを勉強していきたいと思う。

Clojure Programmingあたりをメインに読んでいきたい。