プロジェクトオイラー35問目

プロジェクトオイラー35問目。123、231、312みたいにグルグル回した数字がすべて素数であるものを100万以下のものについて求めよ。

(defn prime? [n]
  (cond
   (> 2 n) false
   (== 2 n) true
   (even? n) false
   (not-any? zero? (map #(rem n %) (range 3 (inc (Math/sqrt n))))) true
   :else false))

(defn rot-numbers [n]
  "Returns the rotations of n. ex) 123 -> 123,231,312"
  (let [s (.toString n)]
    (loop [cnt (count s) num-str s res [s]]
      (if (= cnt 1)
	(distinct (map #(Integer/valueOf %) res))
	(let [new-str (str (apply str (rest num-str)) (first num-str))]
	  (recur (dec cnt) new-str (conj res new-str)))))))

(defn circular-prime? [seq]
  (every? prime? seq))

(def candidates (range 3 1000000 2))

(println
 (count (filter true?
		(map circular-prime?
		     (map rot-numbers candidates)))))

1分ぐらいで答えが出たからいいけど、この場合は素数はエラトステネスのふるいで先に100万まで作った方が速そう。もう1つ、数字として偶数がどこかの桁に含まれるものは最初から除外するといいんだろうけど、かえって遅くなりそうな気もする。

rot-numbersは、もっと細かく関数を切り出したほうが読みやすいのかも。実行効率がさほど問題にならないのなら、それぞれ関数に名前を付けていったほうが後から読みやすそう。