Sieve of Eratosthenes (team assignment)

(a) Recall that a lazy list is a useful structure for representing a long or even infinite list. A lazy list is represented in Scheme with a cons cell, where the "car" contains a data item and the "cdr" contains a function which returns the rest of the lazy list. If the function returns #f, the list is empty. Write the following functions that create and manipulate lazy lists:

• (seq first last)
  This function takes two integers and returns an integer lazy list containing the sequence of values first, first+1, ... , last. This is just a renaming of the function gen-lazy-list from the previous assignment, so this one should be pretty easy.
• (infSeq first)
  This function takes an integer and returns an integer lazy list containing the infinite sequence of values first,first+1, ....
• (firstN lazyList n)
  This function takes a lazy list and an integer and returns an ordinary Scheme list containing the first n values in the lazyList. If the lazy list contains fewer than n values, then all the values in the lazy list are returned. You may assume that n is an integer greater than or equal to 1. If the lazy list is empty, return an empty Scheme list.
• (nth lazyList n)
  This function takes a lazy list and an integer and returns the n-th value in the lazyList (counting from 1). If the lazyList contains fewer than n values, then #f is returned.
• (filterMultiples lazyList n)
  This function returns a new lazy list that has n and all integer multiples of n removed from lazyList. For example, a non-lazy list version of filterMultiples would behave as follows:
  (filterMultiples '(2 3 4 5 6) 2) ---> (3 5)
  (filterMultiples '(3 4 5 6 7 8) 3) ---> (4 5 7 8)

(b) A wide variety of techniques have been devised to compute prime numbers (numbers evenly divisible only by themselves and 1). One of the oldest techniques is the "Sieve of Eratosthenes." This technique is remarkably simple.

You start with the infinite list L = 2, 3, 4, 5, .... The head of this list (2) is a prime. If you filter out all values that are a multiple of 2, you get the list 3, 5, 7, 9, .... The head of this list (3) is a prime. Moreover, if you filter out all values that are a multiple of 3, you get the list 5, 7, 11, 13, 17, .... Repeating the process, you repeatedly take the head of the resulting list as the next prime, and then filter from this list all multiples of the head value.

You are to write an function (primes) that computes a lazy list containing all prime numbers, starting at 2, using the "Sieve of Eratosthenes." To test your function, evaluate (firstN (primes) 10). You should get (2 3 5 7 11 13 17 19 23 29). Try (nth (primes) 20). You should get 71. (This computation may take a few seconds, and do several garbage collections, as there is a lot of recursion going on.)

(Hint: Create a recursive function (sieve lazyList) that returns a new lazy list. The car of this lazy list should indicate the current value, as usual. The cdr should be a function that calls sieve again appropriately.)

---

You must use recursion, and not iteration. You may not use side-effects (e.g. set!).

Submit your code in a file called sieve.rkt.