Sieve of Eratosthenes Algorithm
The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime as composite (i.e., not prime), starting with the multiples of 2.
Here is how the algorithm works:
 Create a list of all integers from 2 to n, where n is the limit of the search.
 Start with the first prime number, which is 2. Mark all multiples of 2 as composite (i.e., not prime ).
 Find the next number in the list that is not marked as composite. This number must be prime. Mark all multiples of this number as composite.
 Repeat step 3 until all numbers up to n have been processed.
 The unmarked numbers are all prime.
Here's how the Sieve algorithm can be implemented using lazy sequences in Clojure:


The sieve function takes a lazy sequence s
and returns a lazy sequence of
prime numbers. The first line of the function extracts the first element of s
,
which must be prime, and assigns it to the variable p
. Then we create a lazy
sequence that starts with p
, followed by the prime numbers generated by
recursively calling sieve with a filtered version of s
that removes all
multiples of p
.
We are not explicitly marking numbers as composite, instead we are filter them
out using mod
function.
The primes
variable is initialized to the lazy sequence of prime numbers
generated by calling sieve with a lazy sequence of all integers starting from 2.
Because the sequence is lazy, only the first few primes are computed and stored
in memory at any given time.
And thus you have an infinite sequences of prime numbers at your hand.