Spring 2000, CSE 428: Assignment 4

Distributed: Feb 24.
Due: Mar 2 in class.
Total maximum score: 100 points.
The purpose of this assignment is to provide experience with OO programming in C++.

An optimized version of the Sieve of Eratosthenes

Consider the Eratosthenes' Sieve based on the Data Driven model described in Class 14 (see the corresponding lecture notes). We want to make the program more efficient by using the following property:

Given two numbers n and k, if n is not a multiple of any prime number smaller than k, and n < k2, then n must be prime.
The idea is that, whenever a filter with parameter (factor) k receives a number n, it should test, additionally, whether n < k2. If this is the case, then we know that the number n is prime. Thus we can print n directly, and create a new filter with factor n at the end of the chain. The optimization consists in the fact that the number n will not have to traverse all the filters which come after filter k in the chain.

Please modify the classes Item, Counter, Filter and EratosthenesSieve of the Data Driven program in the lecture notes so to cope with this optimization. Please add the same main function used in the lecture notes. Modify the format of the output so that, each time a new prime number n is printed, also k (the parameter of the filter which detects that n < k2) is printed.

Your program should give results like in the following sample sessions (assuming that the source code is in a file with name 1001.C): 

   >g++ 1001.C
   >a.out
   Please input the max number to be generated
   10
   The first prime number is 2
   The next prime number is 3 (detected by filter 2)
   The next prime number is 5 (detected by filter 3)
   The next prime number is 7 (detected by filter 3)
   End
   >
   >a.out
   Please input the max number to be generated
   30
   The first prime number is 2
   The next prime number is 3 (detected by filter 2)
   The next prime number is 5 (detected by filter 3)
   The next prime number is 7 (detected by filter 3)
   The next prime number is 11 (detected by filter 5)
   The next prime number is 13 (detected by filter 5)
   The next prime number is 17 (detected by filter 5)
   The next prime number is 19 (detected by filter 5)
   The next prime number is 23 (detected by filter 5)
   The next prime number is 29 (detected by filter 7)
   End
   >

Format of the solution

Please give an hard copy of your source code to the instructor by the due date. Furthermore, you should also email your source code to cg428@cse.psu.edu by the due date, so to allow us to check that your program runs correctly. Please send the code as an attachment (not by "cut-and-paste"), and use the last 4 digits of your student id, followed by ".C", as the filename (example: if the last digits of your id are 1001, then the file should have name 1001.C).

Please make sure that your program can be compiled and executed on Unix and that it is self-contained. Namely, it should contain all the definitions and the main function.

Please use the same names as those used in the lecture notes. You are welcome to use the code of the lecture notes and modify it wherever needed. You can add, of course, new classes, fields, etc. if you need them.

Note: The solution should be based on the program of the lecture notes. . We cannot accept different solutions because we could not be sure that they would be original work: There are plenty of solutions to the Eratosthenes Sieve available in books and on the web...