Skip to content

Instantly share code, notes, and snippets.

@mnzk
Created October 1, 2011 10:30
Show Gist options
  • Save mnzk/1255850 to your computer and use it in GitHub Desktop.
Save mnzk/1255850 to your computer and use it in GitHub Desktop.
Infinity sieve of Eratosthenes . Ver.2
(defn- diff-seq
"Returns a lazy seq of numbers in s1 but not in s2.
Both of s1 and s2 must be increasing monotonically and infinite sequence."
[s1 s2]
(let [x1 (first s1), x2 (first s2)]
(cond
(= x1 x2) (recur (rest s1) (rest s2))
(> x1 x2) (recur s1 (drop-while (partial > x1) s2))
(< x1 x2) (let [[s1a s1b] (split-with (partial > x2) s1)]
(lazy-cat s1a (diff-seq s1b s2))))))
(defn- arithmetic-seq
"Return a lazy arithmetic sequence"
[start step]
(iterate (partial + step) start))
(defn- prime-numbers*
"Returns a lazy seq of prime numbers in nums."
[nums prms-que]
(let [p1 (first prms-que)
p2 (second prms-que)
sieved-nums (diff-seq nums (arithmetic-seq (* p1 p1) p1))
[prms rest-nums] (split-with (partial > (* p2 p2)) sieved-nums)]
(lazy-cat prms (prime-numbers* rest-nums (rest prms-que)))))
(defn prime-numbers
"Return a lazy sequence of prime numbers"
[]
(prime-numbers* (cons 2 (arithmetic-seq 3 2))
(lazy-cat [3 5] (drop 3 (prime-numbers)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment