Project Euler Problem 35

Ivar Thorson bio photo By Ivar Thorson

For problem 35, we need to compute how many circular primes there are below 1,000,000. Circular primes are numbers for which all rotations of a number are also primes, like (197->971->719).

Once again, we exploit all that old code for lazily generating primes to our advantage:

;; From Euler-7
(def primes (lazy-primes-cgrande))

;; From Euler-27
(defn prime? [n]
  (not-any? #(zero? (rem n %)) (take-while #(<= % (Math/sqrt n)) primes)))

(defn rotate-str [s]
  (apply str (concat (rest s) [(first s)])))

(defn circular-prime? [n]
  (every? prime?
          (map #(Integer/parseInt %)
               (take (count (str n)) (iterate rotate-str (str n))))))

(defn euler-35 []
  (count (filter circular-prime? (take-while #(< % 1000000) primes))))

That’s a straightforward definition with reasonable performance. Peeking at clojure-euler, I noticed a function in clojure.seq-utils that could replace the rotate-str, reducing circular-prime? to a one-liner:

use '[clojure.contrib.seq-utils :only (rotations)])

(defn circular-prime? [n]
  (every? prime? (map #(Integer/parseInt (apply str %)) (rotations (str n)))))

Note that this whole program really boils down to two new lines of functionality; everything else is old code borrowed from previous problems or clojure-contrib.