CSCI 362: The Sieve of Eratosthenes
Overview
Implement the Sieve of Eratosthenes using two data types, a set and a
vector. Each implementation will compute the set of prime numbers
between \(2\) and \(N\). Each will take \(N\) as an argument, and return a
std::set
. In main output the COUNT of prime numbers between
\(2\) and \(N\) and the time it took to compute the
count. Even though we are computing the prime numbers themselves, for
this program it is only the count we are concerned with. You will likely
want to print some of the prime numbers when debugging.
For the first implementation, use
std::set
and its iterators. NO mod
operations are allowed, and you must use iterators as described
in class — not satisfying either condition will result in a ZERO. Do NOT
attempt to erase values that are larger than \(N\).
For the second implementation, write a sieve
function that uses a std::vector
to compute the primes.
Maintain the same interface as the function that uses a set. Avoid
erasing elements in the vector, instead marking them as erased (set them
to false
) using boolean values. Again, do NOT use mod operations as they are not part
of the algorithm. Ensure you do NOT consider multiples of composite
numbers (e.g., 4 * 4
, 4 * 5
, …,
6 * 6
, etc.).
Time the sieve algorithms using this Timer
class. Start the timer immediately BEFORE calling your sieve
function, and stop the timer immediately AFTER you obtain the count
(BEFORE doing any output). Obtain your times by averaging over at least
3 trials. Compile with -O3
to obtain timing values.
Create a table of run times for \(N=\) 10, 20, and 40 million using the format below. Include this table in a comment at the BOTTOM of your driver file. DISCUSS your findings, providing AT LEAST TWO reasons why the faster version performs better than the other, mentioning relevant COMPLEXITIES.
N 10,000,000 20,000,000 40,000,000
=============================================
set XXXX.XX XXXX.XX XXXX.XX
vector XXXX.XX XXXX.XX XXXX.XX
DISCUSS FINDINGS HERE.
Input Specification
Take the implementation to use and N from the command line. You may assume N >= 2. For implementation, use “set” or “vector”, EXACTLY as I have them spelled.
./Sieve set 4096
Output Specification
Output N, the count of prime numbers, the implementation used (set or vector), and the time in the format below. Use two digits of precision for the time. The function “Pi” in Mathematica returns “Pi(N)”, the number of primes less than or equal to N.
Use PRECISELY the format below with the EXACT same SPACING and SPELLING.
Pi[4096] = 564 (using a set)
Time: 1.95 ms
Required Methods
Include at LEAST the following methods.
// Return the set of primes between 2 and N.
// Use a set to implement the sieve.
<unsigned>
set(unsigned N);
sieveSet
// Return the set of primes between 2 and N.
// Use a vector to implement the sieve.
// After filtering out the composites, put the primes in a set
// to return to the caller.
<unsigned>
set(unsigned N); sieveVector
Hints
See CommandLineArgs.cc for how to handle command line arguments
Style
Use good programming style:
- Write comments
- Choose mnemonic, meaningful variable names (e.g. balance, interestRate)
- Remember to include a comment block at the top of your program that
includes:
- Your name
- The course
- The last date of modification
- The assignment name
- A brief description of what your program does
- FORMAT YOUR CODE CONSISTENTLY.
Submission
Please submit a single C++ source file to Autolab under the Sieve assignment
Alternatively,
autolab submit NameOfFile.cpp -w
Grading
This assignment is graded out of a total of 75 points
- [30pts] Correctness of
std::vector
version - [30pts] Correctness of
std::set
version - [20pts] Exact Input / Output
- [10pts] Code Formatting / Style / Documentation
- [10pts] Performance table and Discussion of timings
- NOTE: if your program does not compile/run, the highest score you will earn will be a 10/100