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.
set<unsigned>
sieveSet (unsigned N);

// 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. 
set<unsigned>
sieveVector (unsigned N);

Hints

See CommandLineArgs.cc for how to handle command line arguments

Style

Use good programming style:

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