Arantium Maestum

プログラミング、囲碁、読書の話題

Clojureで素数計算

Project Euler第三問から素数が関わってくる問題が始まる。

素数の計算といえば有名どころはエラトステネスの篩だろう。ただ、Haskellで間違った実装が数十年に渡って教えられていたりと、とくに無限に続くようなSieveはなかなかコードが理解しにくい。

Sieveに比べて効率はよくないが算出方法が明快でより直感的な素数計算をClojureで書いてみる。

とどのつまりは素数を2から順に調べていくだけ。数字nを調べる場合、√n以下のこれまで算出された素数のみ使って剰余の有無を確認する。

(defn is-prime [n prime-vec]
  "nが素数であるか否かをn未満のすべての素数のvector
   prime-vecを使って計算"
  (every?
    #(not= 0 (mod n %))
    (take-while
      #(>= n (* % %))
      prime-vec)))

(defn next-prime-vec [prime-vec]
  "2..nまでのすべての素数のvectorを入力として受け入れ
   次に大きい素数を追加した新vectorを返す関数"
  (loop [n (inc (last prime-vec))]
    (if (is-prime n prime-vec)
      (conj prime-vec n)
      (recur (inc n)))))

(def prime-vecs
  (iterate next-prime-vec [2]))

(def primes
  (map last prime-vecs))

2を特別なケースとして扱ってnext-prime-vecをどうにか奇数のみチェックするように変えたいのだが、きれいな書き方が思いつかない。

今回Clojureの特徴的なloop/recurで明示的なtail recursionをやってみたり、fn [x] (logic x)の省略形である#(logic %)という匿名関数構文を使ってみたり、と試してみた。tail recursionは比較的簡単に慣れそう。匿名関数はperlチックでいやぁな感じがする(Python主義者の偏見)。