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 >
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...