For this computer assignment, you are to write and implement a C++ program to find

and print all prime numbers within a range [lower upper] using the algorithm

known as the Sieve of Eratosthenes. The program will have basic interactive user

interface to take input values of lower and upper and allow the user to continue or

quit the game.

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 to contain all of the integers in the

range lower to upper. Note that the smallest prime number is 2. If the value of

lower is less than 2, you need to adjust that. 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 of the 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 lower to upper.

The algorithm uses an optimization feature by only looking at the key values for m

sqrt ( upper ). To implement this, test all numbers m such that m*m upper,

rather than computing the square root of upper.

assignment3.cc is provided to you at the directory:

/home/turing/mhou/public/csci340spring2018.

In this file, the main function is already implemented. You are required to implement the

following functions:

void sieve ( set < int >& s, const int lower, const

int upper ) : This routine can be used to apply the Sieve of Eratosthenes

algorithm to remove all nonprime numbers from the integer set s = {

lower, , upper }.

void print_primes ( const set < int >& s, const int

lower, const int upper ) : This routine can be used to print the

Sieve of Eratosthenes

2

elements in the integer set s (NO_ITEMS = 6 primes per line and ITEM_W

= 4 spaces allocated for each prime).

void run_game ( set& s ) : This routine maintains a loop to take

inputs from a user. The user will be asked for the range of the prime numbers.

If the range is not valid, e.g. lower is greater than upper, the user will be

asked to input again. The routine will invoke sieve() and

print_primes(). Once the results are displayed, the user will be asked

whether to continue or quit the game. In case of continuing the game, the

user will be asked for values of the range again. The game continues until the

user requests to stop.

Programming Notes:

You are required to use the set container to store the prime numbers. In STL, a

set is implemented as an associative container, and duplicate keys are not allowed.

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.

void sieve( set& s, const int lower, const int upper) {

}

void print_primes( const set& s, const int lower, const int upper) {

}

void run_game(set& s) {

}

int main() {

set s;

run_game(s);

return 0;

}

Output:

Please input lower bound and upper bound and hit enter (e.g. 10 100):

There are 25 prime numbers between 1 and 100:

2 3 5 7 11 13

17 19 23 29 31 37

41 43 47 53 59 61

67 71 73 79 83 89

97

Do you want to continue or not? Please answer yes or no and hit enter:

Please input lower bound and upper bound and hit enter (e.g. 10 100):

There are 5 prime numbers between 30 and 50:

31 37 41 43 47

Do you want to continue or not? Please answer yes or no and hit enter:

Please input lower bound and upper bound and hit enter (e.g. 10 100):

There are 32 prime numbers between 200 and 400:

211 223 227 229 233 239

241 251 257 263 269 271

277 281 283 293 307 311

313 317 331 337 347 349

353 359 367 373 379 383

389 397

Do you want to continue or not? Please answer yes or no and hit enter:

____________________________________________________________________________________________

keyboard input:

1 100

yes

30 50

yes

200 400

no