gistfile1.clj

(ns sieve
  (:use clojure.test))

(defn square [x] (* x x))

(defn seq-contains? [ls x]
  (boolean (some #(= x %) ls)))

(defn multiple-of? [product divisor]
  (and (= 0 (mod product divisor))
    (not (= product divisor))))

(defn primes-less-than [n]
  (loop [current-n 2 potential-primes (range 2 n)]
    (if (> (square current-n) n)
      potential-primes
      (if (seq-contains? potential-primes current-n)
        (recur (inc current-n) (remove #(multiple-of? % current-n) potential-primes))
        (recur (inc current-n) potential-primes)))))


(is (= () (primes-less-than 2)))
(is (= '(2) (primes-less-than 3)))
(is (= '(2 3) (primes-less-than 4)))
(is (= '(2 3) (primes-less-than 5)))
(is (= '(2 3 5) (primes-less-than 6)))
(is (= '(2 3 5) (primes-less-than 7)))
(is (= '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47) (primes-less-than 50)))