Previous Page

Sieve of Sundaram - C++ console

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

/*

     NOTE: CODE UPDATED 12-5-14 

 Name: Brian Butler
 Professor: Gary Hartell
 Date: September 22, 2011
 Assignment: Sieve of Sundaram

                             Descripion:
    This program uses the Sieve of Sundaram to find all of the prime numbers up to
    and including the integer entered by the user.

                Algorithm:(taken from Wikipedia.com)

  Start with a list of the integers from 1 to n. From this list, remove all
  numbers of the form i + j + 2ij where:

   1)   i,j Elements of N, 1<= i<=j
   2)   i + j + 2ij <= n

 The remaining numbers are doubled and incremented by one, giving a list of the
 odd prime numbers (i.e., all primes except the only even prime 2) below 2n + 2.

 The sieve of Sundaram is equivalent to the sieve of Eratosthenes, except that
 the initial list corresponds only to the odd integers; the work of "crossing out"
 the multiples of 2 is done by the final double-and-increment step.
 Whenever Eratosthenes' method would cross out k different multiples of a prime 2i+1,
 Sundaram's method crosses out i + j(2i+1) for i <= j <= ( inputNumber / 2).


                  CALCULATIONS BELOW ARE TAKEN FROM:
                http://en.wikipedia.org/wiki/Sieve_of_Sundaram
*/

#include 

using namespace std;

int main()
{
      endl(cout);
      endl(cout);
      cout << "Welcome to the Sieve of Sundaram\n" << endl;

      int inputNumber; // users input
      int totalPrimes = 0; // total number of prime numbers that are found
      int TheseArePrime = 0; // variable used in the array that stores the prime numbers found

      cout << "Input a positive integer to find all the prime numbers up to that number: ";
      cin >> inputNumber;

      if(inputNumber < 1)
      {
          while(inputNumber < 1)
          {
              cout << "Input a positive integer to find all the prime numbers up to that number: ";
              cin >> inputNumber;
          }

      }

       endl (cout);
       
               // CALCULATIONS BELOW ARE TAKEN FROM:
               // http://en.wikipedia.org/wiki/Sieve_of_Sundaram

     int n = inputNumber / 2;

     int isPrime [inputNumber];/* array to start off with that will eventually get
                                    all the composite numbers removed and the remaining
                                    ones output to the screen                        */

//  Fill the array with a list of integers up to the inputNumber  
     for (int i = 0; i < inputNumber; i++)
     {
        isPrime[i] = i + 1;
     }

     for (int i = 1; i < n; i++)
     {
         for (int j = i;  j<= (n-i)/(2*i+1); j++)
         {
            isPrime[i + j + 2 * i * j] = 0;/*From this list, remove all
                                                  numbers of the form i + j + 2ij    */
         }
     }
        if (inputNumber >= 2)
        {
            isPrime[TheseArePrime++] = 2;/*this IF statement adds 2 to the output since 2 is a prime number    */
            totalPrimes++;
        }

         for (int i = 1; i < n; i++)
        {
            if (isPrime[i] != 0)
            {
                isPrime[TheseArePrime++]=i*2+1;
                									/*The remaining numbers are
                                                    doubled and incremented by
                                                    one, giving a list of the
                                                    odd prime numbers (i.e., all
                                                    primes except the only even
                                                    prime 2) below 2n + 2.  
                                                     */

                totalPrimes++;// the counter of the number of primes found
            }
        }

/*  Output Prime Numbers */

        for (int x = 0; x < totalPrimes; x++)
        {
            if (isPrime[x]!= 0)
            {
                cout << isPrime[x]<< "\t";//outputs all prime numbers found
            }
            else
            {
                break;
            }
        }

        cout << "\n\nNumber of Primes: " << totalPrimes << endl;
        			// NOTE: this outputs the number of primes up to number input by the user.
    return 0;
}

// END OF CODE - Only copy code above this comment