A prime number is an integer greater than 1 and divisible only by itself and 1. An integer x is divisible by an integer y if there is another integer z such x = y*z. The Greek mathematician Erathosthenes (pronounced Er-ah–tos-thin- eze) gave an algorithm for finding all prime numbers less than some integer N. This algorithm is called the S ieve of Erathosthenes . It works like this: Begin with a list of integers 2 through N . The number 2 is the first prime. (It is instructive to consider why this is true.) The multiples of 2—that is, 4, 6, 8, etc.—are not prime . We cross these off the list. Then the first number after 2 that was not crossed off, which is 3, is the next prime. The multiples of 3 are not primes . Cross these off the list. Note that 6 is already gone, cross off 9, 12 is already gone, cross off 15, etc. The first number not crossed off is the next prime. The algorithm continues on this fashion until we reach N . All the numbers not crossed off the list are primes.

a. Write a program using this algorithm to find all primes less than a user- upplied number N . Use a vector container for the integers. Use an array of bool initially set to all true to keep track of crossed off integers. Change the entry to false for integers that are crossed off the list.

b. Test for N = 10, 30, 100, and 300.

Improvements:

c. Actually, we do not need to go all the way to N. You can stop at N/2. Try this and test your program. N/2 works and is better, but is not the smallest number we could use. Argue that to get all the primes between 1 and N the minimum limit is the square root of N.

d. Modify your code from part a to use the square root of N as an upper limit.