The Sieve of Eratosthenes is a method to find all prime numbers below a certain value m. First remember that prime numbers are numbers (> 1) that cannot be divided except by 1 or themselves. The first ten primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The idea of the Sieve is as follows. All numbers below m are gathered in a table. Starting from 2 (1 being a special case, it is not a prime), we strikeout all numbers that are multiple of 2, meaning we strikeout every 2 numbers (4, 6, ...). Then we move to the next not stricken-out number (in this case 3), and strikeout all multiples of 3, meaning we strikeout every 3 number (6, 9, . . . ). We move on to the next not stricken-out number (5) and repeat the process. 

A number that we encounter not stricken-out is prime, and should be output as such. The interesting aspect of this algorithm is that it gives out prime numbers without using any division: it only strikes out multiples. The idea of the algorithm being set, lets move to the actual C++ implementation. We will build a single program that will be modified at each question.

1. Write a program that asks the user for the maximal value m as an input > 1 and keeps asking until the input satisfies this condition. It can output the value m just to double check (see left part of Table 1).

 * The Sieve of Eratosthenes * Please input a number (> 1): 0 

Please input a number (> 1): -5 Please input a number (> 1): 1 Please input a number (> 1): 42 The prime numbers smaller than 42 are: 

 * The Sieve of Eratosthenes * Please input a number (> 1): 50 

The prime numbers smaller than 50 are: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,

Table 1: Expected output of the Sieve of Eratosthenes. Left: after Question 1; right: final version.

3. We will use an array of booleans of size m + 1 to represent whether the ith number (it will be at index i so that makes things easier) is a potential prime. Initially all numbers are, except for 0 and 1.

   a) Declare this array. b) Initialize all its values to true.

   c) Change the values of indexes 0 and 1 to false.

5. The core of the algorithm consists in traversing the array using an index i. When encountering a number that is still a potential prime (so the value at index i is true), this i is prime and is output. Then a loop sets all multiples of i as non primes. This is more easily done by thinking of multiples of i as 2i, then 2i + i, 2i + i + i, ...until reaching m. A number that is not a potential prime is simply skipped (nothing is done). Note: you cannot use division (neither / nor %) here!