Sieve of Eratosthenes (individual assignment)
Table of Contents
This assignment is to be done individually. You can talk to other people in the class, me (Dave), and any of the course staff (graders, lab assistants, teaching assistants, prefects) for ideas and to gain assistance. You can help each other debug programs, if you wish. The code that you write should be your own, however, and you shouldn’t directly share your code with others. See the course syllabus for more details or just ask me if I can clarify.
1 Get started
1.1 Use GitHub classroom to create a repository for your assignment
The first thing you’ll need to do is to create a repository for your project using GitHub classroom. Visit this GitHub classroom link (which I’ve placed in Moodle). Log into GitHub if need to. GitHub should then hopefully respond with a screen that says “You’re ready to go!” and will supply you with a link for the repository that you are creating. Click on that link, and you should be taken to the repository.
1.2 Create a repl in Repl.it
Once you see your repository in GitHub (not Repl.it), you should see a button labeled “Work in Repl.it.” Click it. That should set up a new repl in Repl.it, and you should be all set to work. As always, make sure the repl created in Repl.it is private.
2 Main task
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.
2.1 seq
(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 a previous assignment, so this one should be
pretty easy.
2.2 inf-seq
(inf-seq first)
This function takes an integer and returns an integer lazy list containing the
infinite sequence of values first,first+1, ....
2.3 first-n
(first-n lazy-list n)
This function takes a lazy list and an integer and returns an ordinary Scheme list containing the first n values in the lazy-list. 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.
2.4 nth
(nth lazy-list n)
This function takes a lazy list and an integer and returns the n-th value in the
lazy-list (counting from 1). If the lazy-list contains fewer than n values, then
#f is returned.
2.5 filter-multiples
(filter-multiples lazy-list n)
This function returns a new lazy list that has n and all integer multiples of
n removed from lazy-list. For example, a non-lazy list version of
filter-multiples would behave as follows:
(filter-multiples '(2 3 4 5 6) 2) ---> (3 5) (filter-multiples '(3 4 5 6 7 8) 3) ---> (4 5 7 8)
3 Sieve of Eratosthenes
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.” Here’s how it works.
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. Here are some sample usages:
(first-n (primes) 10) ---> (2 3 5 7 11 13 17 19 23 29)=. Try (nth (primes) 20) ---> 71
(Possibly useless hint: Create a recursive function (sieve
lazy-list) that “sieves” the first item from the rest, returning a new lazy
list. It uses filter-multiples, but adds an additional recursive operation.)
4 Capstone work
Work in this section is 100% optional, and doesn’t contribute towards your grade. Nonetheless, if you’re looking for an extra challenge, these are fun additional exercises to try.
4.1 count-smaller-primes
Create a function called count-smaller-primes that takes a single integer as a parameter, and counts the number of primes less than that number. For example:
(count-smaller-primes 11) ---> 4
You should be using your lazy list of primes to do this, rather than some other technique that generates prime numbers.
4.2 twin-primes
Create a function called twin-primes that generates an infinite lazy list of all twin prime pairs, in order. Twin primes are two prime numbers that are only two apart from each other. For example:
(first-n (twin-primes) 5) ---> ((3 . 5) (5 . 7) (11 . 13) (17 . 19) (29 . 31))
5 Other info
You must use recursion, and not iteration. You may not use
side-effects (e.g. set!).
6 How to test and submit your work
Go back and look at the sections at the end of Scheme Lab 2 labeled “How to test your work” and “How to submit your work.” Those should apply identically here. Follow those instructions, and you should hopefully be all set.