Csc 125 online - Computer Science II, Programming in C++
Project 1 
Due: Sunday, September 10, 2006 (Monday at 3:00 am)

A Sieve of Eratosthenes Abstract Data Type

 

Sieve of Eratosthenes

The ancient Greek mathematician Euclid described a simple way to determine the prime numbers.  He imagined lining up a large number sticks, stuck upright in the ground, with a way to keep track of the number of each stick in line.  Then he would remove the first stick, because 1 is not a prime number, by definition.   Starting with 2,  he would knock over every second stick, because they must be divisible by 2 and therefore not prime.  He would go back to 2 and find the next stick standing, which would be 3.  So he would then knock over every third stick above 3, if it wasn't already knocked over, because they must be divisible by 3.  Going back to 3, the next stick still standing must be prime, because it was not a divisible by any of the previous primes.  That number would be 5, so he would knock down every fifth stick above 5.  He then find 7 still standing and would knock down every seventh stick still standing above 7.  Then every 11th stick above 11, and so on.  After finding the first prime above the square root of the number of sticks originally stuck in the ground, all of the rest of the sticks still standing must represent a prime.  If the there were a composite number above the square root of the number of sticks, then one of its factors must be smaller than the square root.  Multiplying two numbers above the square root of the number of sticks would always produce a number greater than then number of sticks.

This algorithm is easily implemented on a computer by using an array to represent all the sticks.   Kicking over the sticks then becomes a loop within a loop.  The outer loop represents finding the next stick still standing, which must be a prime number, and the inner loop represents kicking over every prime_number_th stick in the rest of the array.

Assignment

Write a complete C++ program that implements an Abstract Data Type (i.e. a class) that implements a prime number generator using Euclid's Sieve of Eratosthenes algorithm.  Your class must implement (i.e. have a method for) at least the following capabilities:

    - The Constructor must initialize all variables, including the int array in preparation for the Sieve of Eratosthenes algorithm.
    - It must run the Sieve of Eratosthenes algorithm to fill an int array of primes up to a max number supplied by the programmer using this class (in this case you, when you write  int main() ).
    - It must print to the screen all the primes between (and including) a lower and upper limit supplied by the programmer using this class (in this case you, when you write  int main() ).
    - It must fill an array passed to it as a method's parameter with all the primes from 2 to the max number above.  There must be no empty or non-prime numbers in the array, except contiguously at the end of the array.  (i.e. you must eliminate the array elements that represent knocked-down sticks).
    - It must determine if a number passed to it as a method's parameter is prime or not. 

  

Requirements

You may use code that implements the Sieve of Eratosthenes which you get from me, or any code which you get from an outside source, such as the Internet.  You may use only code that implements the actual Sieve algorithm, not code that implements the Abstract Data Type as required by this project.  I am developing code in C for the Sieve algorithm as part of the classroom section of Csc 125.  You may find it in my directory   ~sbadman/csc125traditional/project1start/   Of course you must understand any code you get, and properly adapt it for use in your program.   You may find it easier to simply write your own code for the Sieve of Eratosthenes algorithm.

Also, your class must print to the screen in two of its methods, but it does not have to get any input from the user.  What numbers to use, and where they come from, is the decision of the programmer using your class.  In this case, the numbers come from  int main().

Your program cannot use any global variables.

Your project must implement the concepts of Data Encapsulation inside a well designed Abstract Data Type.

The code that actually implements the Sieve of Eratosthenes, must be in a private method called from inside one of your public methods.

All data stored inside your class must be private.

Your  int main() must be a short simple function definition that merely creates a object of your class, and then tests it by calling all of its public methods.  You may use the following code as a guide to what your  int main() should be:  example int main() for Project 1.

Your program must be in at least three files, a .h and a .cpp file for your class that implements the Abstract Data Type and a .cpp file for the int main().

Your program must be written for a Linux system, using ANSI C++ and good Object Oriented C++ programming style.  Before grading, you must  check it on Parkland's Linux computers for proper operation.   You may not use any non-ANSI C or C++ extensions.


 Grading

Project 1 is worth 16 points toward the final grade.  It will be graded according to the criteria on the Project 1 Grading Criteria. 


 Date

Your project must be properly submitted into the ~sbadman/csc125/students/project1/  directory by 3:00 am Monday, September 11th.   You may have your project graded before September 11th, if you wish, by making arrangements with the instructor.  If you have your project graded early, you will still have until 3:00 am Monday to re-submit your program with corrections. 

  
Back to Csc 125 - Computer Science II, Programming in C++
  Scott Badman   Office: B132   Phone: 353-2250   sbadman@parkland.edu  

Parkland College, 2400 W. Bradley Avenue, Champaign, IL 61821