PRIME SIEVE ALGORITHM ( SIEVE OF ERATOSTHENES )

first-attempt.clj

(defn filter-multiple [n v]
  (if (= 1 n) v
      (filter (fn [x]
                (or
                 (= x n)
                 (not= 0 (mod x n)))) v)))

(defn sieve [input]
  (let [limit (Math/sqrt input)
        numbers (range 2 input)]
    (reduce (fn [acc v]
              (if (>= v limit)
                acc
                (filter-multiple v acc))) numbers numbers)))

second-attempt.clj

(defn sieve [input]
  (let [numbers (set (range 2 (inc input)))
        limit (Math/sqrt input)]
    (reduce (fn [acc n]
              (if (> n limit)
                acc
                (let [multiples (set (range (* 2 n) (inc input) n))]
                  (clojure.set/difference acc multiples)))) numbers numbers)))

(comment
  (clojure.set/difference #{3 6 9} (set (range (* 2 3) 10 3)))
  (time (count (sieve 1000000)))
  (clojure.set/difference (set (range 2 100 1)) (set (range 2 100 2)))
  (filter (set (range 2 100 1)) [1 2 3 4 5 6 7])
  (set (range 2 100 2))
  (filter-multiples 3 [3 6 9 10])
  (mod 10 3)
  (inc 5)
  (range 0 5)
  (sieve 100))