Project Euler #7

2023-05-15

The problem description of Project Euler #7 is very simple and the minimum amount of work needed to just get the solution is not that much. The problem asks:

What is the 10,001st prime?

Initial Solution

My initial solution, although a bit naive, gets the job done relatively quickly for the small case:

(defn primes [n]
  (loop [m 2 primes []]
    (if (>= (count primes) n)
      primes
      (if (every? #(not= 0 (mod m %)) primes)
        (recur (inc m) (conj primes m))
        (recur (inc m) primes)))))

(defn euler-7 [n]
  (last (primes n)))

(time (euler-7 10001))  ;"Elapsed time: 1275.52175 msecs"
                        ;=> 104743
(time (euler-7 100001)) ;"Elapsed time: 78250.286791 msecs"
                        ;=> 1299721

The idea of the primes function being to calculate the first n primes by using the primes that have already been calculated.

While this solution works, there is a lot to improve. Especially regarding time complexity.

Structure

One thing to do to enhance the structure of this code would be to remove the need for parameters in primes by returning an infinite lazy-seq of primes. A direct conversion looks something like this:

(defn lazy-primes
  ([] (lazy-primes 2 []))
  ([m primes] (if (every? #(not= 0 (mod m %)) primes)
                (cons m (lazy-seq (lazy-primes (inc m) (conj primes m))))
                (lazy-primes (inc m) primes))))

This way our euler-7 function looks like:

(defn euler-7 [n]
  (nth (lazy-primes) (dec n)))

(time (euler-7 10001))  ;"Elapsed time: 904.616083 msecs"
                        ;=> 104743
(time (euler-7 100001)) ;"Elapsed time: 101634.307375 msecs"
                        ;=> 1299721

A lot cleaner. A pinch faster for the small case. A lot slower for the big case.

Speed

An easy way to greatly increase the speed of the lazy-primes function is to replace the (every? #(not= 0 (mod m %)) primes) with a better way to check if a number is prime. One such way is this prime? function:

(defn prime? [n]
  (cond
    (<= n 1) false
    (= n 2) true
    :else (every? #(not= 0 (mod n %)) (range 2 (inc (Math/sqrt n))))))

So lazy-primes looks like this:

(defn lazy-primes
  ([] (lazy-primes 2 []))
  ([m primes] (if (prime? m)
                (cons m (lazy-seq (lazy-primes (inc m) (conj primes m))))
                (lazy-primes (inc m) primes))))

And performance looks like this:

(time (euler-7 10001))  ;"Elapsed time: 125.203 msecs"
                        ;=> 104743
(time (euler-7 100001)) ;"Elapsed time: 3076.132458 msecs"
                        ;=> 1299721

Much better. Especially for the big case.

Adding some more optimizations to the prime? function like so:

(defn prime? [n]
  (cond
    (<= n 1) false
    (<= n 3) true
    (zero? (mod n 2)) false
    (zero? (mod n 3)) false
    :else (every? #(and (not= 0 (mod n %))
                        (not= 0 (mod n (+ 2 %))))
                  (range 5 (inc (Math/sqrt n)) 6))))

Yields a respectable runtime:

(time (euler-7 10001))  ;"Elapsed time: 52.351334 msecs"
                        ;=> 104743
(time (euler-7 100001)) ;"Elapsed time: 787.097375 msecs"
                        ;=> 1299721