CS 251: Programming Languages
Spring 2018
hw5: Sieve of Eratosthenes
Due: Wednesday, 04/11 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 a recent 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 integern
is not (evenly) divisible by the integerd
.(not-divisible-by d)
The curried version ofnot-divisible?
. That is, a higher-order function, so that(not-divisible-by d)
is a predicate for non-divisibility byd
. For example,(not-divisible-by 2)
is a function equivalent toodd?
, 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 usesieve
, you may or may not want to recursivelysieve
the rest of the lazy list.
5. Optional Challenges
(factor n)
Return a (Scheme) list of the prime factors ofn
.- 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. We will be grading this using Moodle's anonymous grading capabilities, so make sure that your names are not included in your file.
Start early, have fun, and discuss questions on Moodle.