COS 371: Programming Languages

Spring 2022

hw5: Sieve of Eratosthenes

Due: Friday, 02/25 at 22:00

This assignment is to be done individually. You can share ideas and thoughts with other people in the class, but you should code your own assignment.

1. Goals

To build an infinite list of primes using an ancient algorithm.

2. Introduction

Recall that a prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. A wide variety of techniques have been devised to compute prime numbers. One of the oldest techniques is the Sieve of Eratosthenes, which is remarkably simple:

Start with the infinite list 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.

This is the Sieve of Eratosthenes, one of the earliest known algorithms, dating back to about 200 BC, and is named after the eponymous Greek mathematician who lived around then. See this article for an animation of the process.

3. Specification

(primes)
A zero-parameter function that computes a lazy list containing all prime numbers, starting at 2, using the Sieve of Eratosthenes. For example:
```
(first-n (primes) 10)  --> (2 3 5 7 11 13 17 19 23 29)
(nth (primes) 20)      --> 71
(nth (primes) 1234)    --> 10061
```

4. Notes

You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
You should liberally reuse code from the previous assignments.
In particular, you will want to use lazy-filter. You may also find some of the following helper functions useful.
(not-divisible? d n)
A predicate that says the integer n is not (evenly) divisible by the integer d.
(not-divisible-by d)
The curried version of not-divisible?. That is, a higher-order function, so that (not-divisible-by d) is a predicate for non-divisibility by d. For example, (not-divisible-by 2) is a function equivalent to odd?, so that
```
(not-divisible-by 2)       --> #<procedure>
((not-divisible-by 2) 3)   --> #t
((not-divisible-by 2) 4)   --> #f
((not-divisible-by 3) 5)   --> #t
((not-divisible-by 3) 6)   --> #f
```
(sieve llst)
A function that takes a lazy list and "sieves" the first item from the rest, returning a new lazy list. Depending on how you plan to use sieve, you may or may not want to recursively sieve the rest of the lazy list.

5. Optional Challenges

(factor n)
Return a (Scheme) list of the prime factors of n.
Solve Project Euler #3 (in Scheme, of course). If you are bored and want more practice, feel free to solve even more Project Euler questions.

6. Submission

Submit your code in a file called sieve.scm.

Start early, have fun, and discuss questions on Moodle.