CSCI 340-3-assign03 - Solved

#  Sieve of Eratosthenes

For this computer assignment, you are to write and implement an interactive C++ program to find and print all prime numbers, which are less than or equal to a given value of **n**, using the algorithm known as the *Sieve of Eratosthenes*.

A prime number **p** is an integer greater than **1** that is divisible only by **1** and **p** (itself). The algorithm begins by initializing a set container to contain all the integers in the range **2** to **n**. A loop makes multiple passes over the elements in the set, using successive integer key values 2, 3, 4, ... Each pass *shakes free* nonprime numbers and lets them *filter through the sieve*. At the end, only the prime numbers remain.

Begin with the integer `m = 2`, which is the smallest prime number. The pass scans the set and removes all multiples of 2, having the form `2 * k` for `k >= 2`. The multiples cannot be prime numbers, because they are divisible by 2. 

At the end of the pass, we have removed all even numbers except 2. Next, look at the integer `m = 3`, which is a prime number. As with value `2`, remove all multiples of 3, having the form `3 * k` for `k >= 3`. The multiples 12, 18, and so forth, are even numbers, so they have already been removed from the set. 

The next key integer is `m = 4`, which is no longer in the set, because it was removed as a multiple of 2. The pass takes no action. The process continues until it removes all multiples of prime numbers. In other words, for integer m, remove all multiples of m, having the form `m * k` for `k >= m`. The numbers that remain in the sieve are the prime numbers in the range 2 to n.

The algorithm uses an optimization feature by looking at the key values for `m <= sqrt(n)`. However, in your implementation, test all numbers m such that `m * m <= n`, rather than computing the square root of n.

Starter code for `assignment03.cc` is provided for you as part of this repository, it contains the main function. You will then need to add additional code to the `main()` routine. This code will create an empty set of integers, prompt the user for the upper limit of numbers that you will search for prime numbers and then call the subroutine `sieve()` to execute the *Sieve of Eratosthenes*. The main then calls the subroutine `print_primes()` to print the prime numbers on stdout.

Use a set container to store the prime numbers. In the STL, a set is implemented as an associative container, it uses the model of a mathematical set, it stores keys that are objects of a specified data type, where duplicate keys are not allowed. To use a set in your program, you need to insert the statement `#include <set>` which is already defined in `assignment03.cc`.

In addtion to adding code to `main()`, you are required to implement the following functions:

- `void sieve(set<int> &s, int n)`: This routine can be used to apply the *Sieve of Eratosthenes* algorithm to remove all nonprime numbers from the integer set `s = {2, 3, ..., n}`.

- `void print_primes(const set<int> &s)`: This routine can be used to print the elements in the integer set `s` with `NO_ITEMS = 16` primes per line and `ITEM_W = 5` spaces allocated for each prime.

**Programming Notes:**

* Include any necessary headers and add necessary global constants. 

* You are not allowed to use any I/O functions from the C library, such as `scanf` or `printf`. Instead, use the I/O functions from the C++ library, such as `cin` or `cout`.

* Add documentation to your source file (e.g. https://google.github.io/styleguide/cppguide.html#Comments).

.

.