Previous Page

Sieve of Eratosthenes - C++ console

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