Prime Number Iteration

As a way to practice solving problems in Clojure I've been working on the first several problems of Project Euler. Problems 7 and 10 are much easier to complete if you can easily iterate through prime numbers in sequence:

[2 3 5 7 11 13 17 19 ...]

The internet is full of tutorials and information on prime numbers. Rather than rip off someone else's Clojure code for iterating prime numbers I decided to write my own code based on algoriths presented in non-functional languages.

This post seemed like a good place to start:

https://stackoverflow.com/questions/9625663/calculating-and-printing-the-nth-prime-number/9704912#9704912

The basic idea presented by Daniel Fischer in that post is to iterate from 2 to some upper threshold, testing each number for primality. He provides an example of what that might look like in a language like Java:

public static int nthPrime(int n) {
    int candidate, count;
    for(candidate = 2, count = 0; count < n; ++candidate) {
        if (isPrime(candidate)) {
            ++count;
        }
    }
    return candidate-1;
}

Clojure favors lazily-generated collections so I chose to omit any upper threshold:

(defn primes []
  (filter is-prime? (iterate inc 2)))

So succinct!

Yeah, but what's the (iterate inc 2) thing all about?

Oh, that. Well, I originally wanted to use (range) but there's no way to specify a start without also specifing a stop when using (range). In retrospect I suppose I could have used (drop 2 (range)). Anyway, (iterate inc 2) is synonomous with (range 2 ∞).

From there it's trivial to define a function to retrieve the nth prime (Problem 7):

(defn nth-prime [n]
  (nth (primes) (dec n)))

Problem 10 requires the sum of all prime numbers less than two million:

(defn sum-of-primes-below [n]
  (apply + (take-while #(< % n) (primes))))

Well, that about 'sums' it up! (Hah! See what I did there? The way I used the term 'sum' right after code that uses (apply + ...)? I sure do crack myself up sometimes...) Well, have a nice da

Hey, wait a minute! Your primes function referenced another function called is-prime? but you haven't shown that... I bet you haven't even solved the project Euler problems!

Woah, calm down! Of course I've solved them. You're right--I did sort of gloss over that function. This is the part where the cost in terms of complexity can really skyrocket if you go for the very fastest approaches. Fortunately, these Project Euler don't really require that (yet??).

So, here's the Java code I translated (from that same post mentioned earlier):

private static boolean isPrime(int n) {
    if (n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    int step = 4, m = (int)Math.sqrt(n) + 1;
    for(int i = 5; i < m; step = 6-step, i += step) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

As far as performance goes, this 'middle-of-the-road' implementation gets the job done and isn't too hard to understand:

1. Toss out all multiples of 2 (except for 2 itself).
2. Toss out all multiples of 3 (except for 3 itself).
3. Starting at 5,
4. ...scan up to the square root of n,
5. ...stepping in alternating increments of 2 and 4,
6. ...each time dividing n by i.
7. If the division operation yields no remainder at any point, n is NOT prime.
8. If the loop concludes with each and every division operation yielding a non-zero remainder, n IS prime.

Here's what the same algorithm looks like in Clojure: (The numbered comments below correspond with the numbered list above.)

(defn is-prime? [n]
  (cond
    (zero? (mod n 2)) (= n 2)           ; [1]
    (zero? (mod n 3)) (= n 3)           ; [2]
    :else
    (let [ceiling (inc (Math/sqrt n))]  ; [4]
      (loop [step 2                     ; [5]
             i    5]                    ; [3]
        (if (>= i ceiling)
          true                          ; [8]
          (if (zero? (mod n i))         ; [6]
            false                       ; [7]
            (recur
              (if (= step 2) 4 2)       ; [5]
              (+ i step))))))))

Not the prettiest thing I've ever written, but it's not so bad.

Hah! So much for clojure being so succinct! Your version is 4 lines longer than the Java code...

I guess you can't please everybody. The formatting above allowed for the comments/annotations. FWIW, depending on how you like to format your code some of those expressions could definitely be made into one-liners:

(defn is-prime? [n]
  (cond (zero? (mod n 2)) (= n 2)
        (zero? (mod n 3)) (= n 3)
        :else (let [ceiling (inc (Math/sqrt n))]
                (loop [step 2 i 5]
                  (if (>= i ceiling) true
                    (if (zero? (mod n i)) false
                      (recur (if (= step 2) 4 2) (+ i step))))))))

-Michael Whatcott