Copy and Paste the following code into your favorite C++ Integrated Development Environment (IDE) - compile and run.

/* Name: Brian Butler Professor: Gary Hartell Date: September 21, 2011 Assignment: Sieve of Eratosthenes Descripion: This program uses the Sieve of Eratosthenes to find all of the prime numbers up to and including the integer entered by the user. Algorithm:(taken from Wikipedia.com) 1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n) 2. Initially, let p equal 2, the first prime number 3. Stating from p, count up by p and cross out thus found numbers in the list (which will be 2p,3p,4p, etc.) 4. find the first number not yet crossed out after p; let p now equal this number ( which is the next prime) 5. Repeat steps 3 and 4 until p is greater than n 6. All the numbers in the list whhich are not crossed out are prime */ #include <iostream> #include <cmath> #include <iomanip> using namespace std; int main() { endl(cout); endl(cout); cout << "Welcome to the Sieve of Eratosthenes\n" << endl; int arraySize; int numberPrimes = 0; cout << "Input a positive integer to find all the prime numbers up to and " << "\nincluding that number: "; cin >> arraySize; endl (cout); int y = (int) sqrt(arraySize); bool notPrime [arraySize]; for (int num = 2; num <= y; num++)/* will run through the entire for loop as long as num is less than or equal to the user supplied arraySize. Must start with 2 for it to work, though. */ {//start FOR loop if (!notPrime[num]) /* if the array's expression (num) is NOT not prime then it will prlong out the prime number. So these numbers will be prime and then numbers that are divisible by this number will be put in the notPrime array. Without this if statement, the program will print every number in the array starting with 2 */ {//start IF cout << num << "\t" << flush;/* Outputs each Prime Number. The number 2 prints right away. */ numberPrimes++; notPrime[num] = true;/* THE NUMBERS ADDED HERE ARE ACTUALLY PRIME ----------------------------------------------- This is here to get rid of primes that have already been output to the screen.Without this, there will be some duplicates output to the screen. Basically,if the user inputs a number that is a prime number squared, as the arraySize, the square root of that number will be outputted twice. For Example: if they input 49 as the array size, since 7 is prime and is the square root of 49, it will be output twice. -------------------------------------------------*/ for (int k = num*num ; k <= arraySize; k += num) /* sets k equal to 2 times 2 initially. So k = 4 and 4 will be discarded into the notPrime array. k then updates to k + num (which is 4 + 2). So now 6 is discarded..and so on.Until k is greater than the users input for the arraySize. This FOR LOOP gets rid of all of the multiples of the prime number that has just been outputted. */ { notPrime[k] = true;//numbers not primes go here } }//end IF }//end FOR loop for (int num = y; num <= arraySize;num++) { if (!notPrime[num]) { cout << num << "\t" << flush; numberPrimes++; } } cout << "\n\nNumber of Primes: " << numberPrimes << endl; return 0; } //END OF CODE