Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm for calculating all the prime numbers up to a given value.

In Clojure a naive sieve algorithm might look a little like this:

(defn isprime [p]
  (and (> p 1)
       (every? (fn [x] (not (zero? (rem p x)))) (range 2 (inc (Math/sqrt p))))))

(defn sieve [x]
  (filter isprime (range 1 x)))

A number X is prime if it is only divisible by itself and items in the range 2 to Sqrt( X ). We can then apply the filter function.

We can use this in the REPL and see that it's suprisingly fast:

user> (time (count (sieve 1000)))
"Elapsed time: 1.18792 msecs"
167

user> (time (count (sieve 1000000)))
"Elapsed time: 7990.35914 msecs"
78497

This isn't in fact the Sieve algorithm at all. We recalculate the primes each time so calculating the next prime doesn't take into account the previous ones...

The Genuine Sieve of Eratosthenes (also discussed at LtU) gives some ideas on how to get it going faster...