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