CSC 269 Programming Project. Sieve of Eratosthenes.
First part: due Tuesday January 28, 2003.
Second part: due Thursday January 30, 2003.
-
Problem:
-
Use the algorithm of Eratosthenes to find all prime numbers up to 100.
-
Learning Objectives:
-
Refresh your memory of C++.
-
Refresh your memory of array implementation and linked list implementation
of a list.
-
Learn interface discipline needed for successful programming teamwork.
-
The Algorithm:
-
We use a variation of the algorithm of
Eratosthenes, a prominent philosopher
who lived in Ptolmaic Egypt in the third century BC, and who was the first
to accurately measured the size of the Earth.
-
An integer is defined to be prime if it is greater than 1
and cannot be written as the product of two smaller positive integers.
-
The definition of prime can be made recursive in order to simplify the
calculation, namely by observing that a positive integer n is prime if and
only if it is greater than 2 and is divisible by no prime
whose square does not exceed n.
-
For example, to determine that 97 is prime, after we have already found all
primes less than 97, we need only check whether 97 is divisible by 2, 3, 5,
or 7. We do not need to check whether 97 is divisible by any composite
number, since if 97 is divisible by a composite number it must also be
divisible by a prime number. Likewise, we do not need to check whether
97 is divisible by 11 or any higher prime, since the square of 11 is larger
than 97.
-
Our algorithm works as follows. We initialize a list of primes to be empty.
Then, for all integers n from 2 to 100 (or whatever we stop at) we check
to see whether n is divisible by some i in the list. We do this by running
through the list in order, stopping when we find a divisor or when we find
an i whose square is larger than n. If A divisor was not found, n is
appended to the list. The list is ordered, since items are appended in
order.
-
Implementation:
- The list of primes is implemented in one of two ways in the program,
either as a linked list or as an array. You are familiar with both
implementations from CSC 136.
-
There will be class List, which will have methods as declared in the
prototype in the file List.h. The algorithm uses these methods, but
the implementation is hidden.
-
Files Given:
-
main.cpp
-
List.cpp
-
List.h
-
Sieve.h
-
SieveImpl.h
-
SieveImpl.cpp
-
The First Part of the Assignment:
-
Write additional files as needed so that the entire program runs correctly
if all your files and the six given files are stored in the same directory,
using an array implementation of the data type List.
It will be necessary to create a dummy file called LinkList.h.
-
In case you are rusty on inheritance, I have provided
an unfinished version of ArrayList.h
-
Here is
A running version of the program.
-
Here is
what the output should look like.
-
Turn in:
-
Email your files to the graduate assistant, Doina Bein,
by midnight, Tuesday, January 28. The address is siona@cs.unlv.edu.
You must email from your engineering college account.
Send the files as plain text in the body of the mssage, or as an
attachment, but not using Word or anything else.
-
I don't want anyone's program to resemble anyone else's program.
Try to be unique.
-
It is a bad idea to permit anyone else to have an electronic copy of
your program.
-
-
My Version of the Files You Should Have Written for the First Part of the Assignment:
-
ArrayList.h
-
ArrayList.cpp
-
The Second Part of the Assignment:
-
Write additional files as needed so that the entire program runs correctly
if all your files and the six given files are stored in the same directory,
using a linked list implementation of the data type List.
-
Here is
what the output should look like.
-
Destructors:
-
You do not need to write a destructor for your linked list type. I plan to put
that requirement into the next programming assignment.
-
Turn in:
-
Email your files to the graduate assistant, Doina Bein,
by midnight, Thursday, January 30. The address is siona@cs.unlv.edu.
You must email from your engineering college account.
Send the files as plain text in the body of the mssage, or as an
attachment, but not using Word or anything else.
-
I don't want anyone's program to resemble anyone else's program.
Try to be unique.
-
It is a bad idea to permit anyone else to have an electronic copy of
your program.
-
My Version of the Files You Should Have Written for the Second Part of the Assignment:
-
LinkNode.h
-
LinkList.h
-
LinkList.cpp
