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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

  (defn sieve
    [s] ;; accepts a lazy sequence
    (let [p (first s)]
      (lazy-seq
        (cons p ;; start with p followed by result of recursively calling sieve
              (sieve (filter #(not (zero? (mod % p)))
                               (rest s)))))))

  (def primes (sieve (iterate inc 2)))

  (take 10 primes) ;; (2 3 5 7 11 13 17 19 23 29)

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.