CSC 243 Introduction to Programming
Homework 6
Due by 5:45pm on Tuesday, October 30
Reading
Read Sections 7.1, 7.2, 7.3, 10.1 of the textbook.
Exercises
Solve the following by implementing the corresponding functions in
module homework6.py.
5.49, 6.34, 6.35 (use file clear.txt for
testing), 10.12, 10.17
Extra (optional) problem:
The Sieve of Erastophenes is
an algorithm --
known to ancient Greeks -- that finds all prime numbers up to a
given
number n. It does this by first creating a list L from 2 to n and an
(initially empty) list primeL. The algorithm then takes the first
number in list L (2) and appends it to list primeL, and then removes
2 and
all its multiples (4,6,8,10,12, ...) from L. The algorithm then
takes the new first number in L (3) and appends it to list primeL,
and then
removes from L 3 and all its remaining multiples (9,15,21,...). So,
in every
iteration, the first number of list L is appended to list primeL and
then it and its multiples are removed from list L. The iterations
stop
when list L becomes empty. Write a function sieve that
takes as input a positive integer n, implements the above algorithm,
and returns a list of all prime numbers up to n.
Usage:
>>> sieve(56)
[2, 3, 5, 7, 11, 13, 17, 19,
23,
29, 31, 37, 41, 43, 47, 53]
>>> sieve(368)
[2, 3, 5, 7, 11, 13, 17, 19,
23,
29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
137,
139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
211,
223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283,
293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367]
>>> sieve(32)
[2, 3, 5, 7, 11, 13, 17, 19,
23,
29, 31]
Please use the discussion forum on COL to discuss this
assignment between yourselves and with me. Submit the file homework6.py only through COL.