Project Euler Problem 27

Ivar Thorson bio photo By Ivar Thorson

Project Euler Problem 27 asks us to find the coefficients of a formula that will produce as many prime numbers as possible for consecutive integer values that are inputs.

A brute force approach is concise and all we need to solve the problem. See problem 7 for the definition of lazy-primes-cgrande.

(def primes (lazy-primes-cgrande))

(defn prime? [n]
  (not-any? #(zero? (rem n %)) (take-while #(<= (* % %) n) primes)))

(defn gen-quadratics [a b]
  (map (fn [n] (+ (* n n) (* a n) b)) (iterate inc 0)))

(defn euler-27 []
  (let [quads (for [a (range -1000 1000)
                    b (range -1000 1000)]
                [a b (count (take-while #(and (> % 0)
                                              (prime? %))
                                        (gen-quadratics a b)))])
        [a b _] (reduce #(if (> (nth %1 2) (nth %2 2)) %1 %2) quads)]
    (* a b)))

I don’t see any obvious algorithmic improvements at this point that would reduce the amount of computation necessary to perform. Anybody else see one?