Previous Page

Sieve of Atkins - 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: October 20, 2011
 Assignment:Sieve of Atkin

					   					 Descripion:
		This program uses the Sieve of Atkin 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 result list filled with 2, 3, and 5.
		2. Create a sieve list with an entry for each positive integer;
			all entries of this list should initially be marked nonprime.
		3. For each entry number n in the sieve list, whith modulo-sixty remainder r:
			a. If r is 1,13, 17, 29, 37, 41, 49, or 53, flip the entry for each
				possible solution to 4x^2 + y^2 = n
			b. If r is 7, 19, 31, or 43, flip the entry for each possible solution
				to 3x^2 + y^2 = n
			c. If r is 11, 23, 47, or 59, flip the entry for each possible solution
				to 3x^2 - y^2 = n when x > y
			d. If r is something else, ignore it completely
		4. Start with the lowest number in the sieve list.
 		6. Include the number in the results list.
        7. Square the number and mark all multiples of that square as nonprime.
        8. Repeat steps five through eight.
*/



	#include <liostream>
	#include <cmath>
	#include <conio.h>

using namespace std;

void findPrimes(int arraySize);

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

     int arraySize;
     int numberPrimes = 2;

     cout << "Input a positive integer to find all the prime numbers up to and "
          << "\nincluding that number: ";

     cin >> arraySize;
     endl (cout);

/**************************************************************************************
	              CALCULATIONS IN BELOW METHOD TAKEN FROM:
	            http://en.wikipedia.org/wiki/Sieve_of_Atkin
			      AND TURNED INTO A C++ PROGRAM
**************************************************************************************/
    int sqrtArraySize;
    bool isPrime [arraySize] ;

    for (int i = 0; i <= arraySize; i++)
    {
        isPrime[i] = false;
    }

    sqrtArraySize = sqrt(arraySize);
/**************************************************************************************
					 put in candidate primes:
					 integers which have an odd number of
					 representations by certain quadratic forms
**************************************************************************************/
for (int x = 1; x <= sqrtArraySize; x++)
{
        for (int y = 1; y <= sqrtArraySize; y++)
        {
            int n = 4 * x * x + y * y;

                    if (n <= arraySize && (n % 12 == 1 || n % 12 == 5))
                    {
                        isPrime[n] = !isPrime[n];
                    }

                    n = 3 * x * x + y * y;

                    if (n <= arraySize && (n % 12 == 7))
                    {
                        isPrime[n] = !isPrime[n];
                    }

                    if (x > y)
			        {
                        n = 3 * x * x - y * y;

                            if (n <=arraySize && n % 12 == 11)
                            {
                                isPrime[n] = !isPrime[n];
                            }
			        }
        }//end 2nd FOR LOOP
}//end 1st FOR LOOP

/***************************     Eliminate composites by sieving    ******************/
for (int n = 5; n <= sqrtArraySize; n++)
{
        if (isPrime[n])
        {
            int omit = n * n;

                    for (int k = omit; k <=arraySize; k +=omit)
                    {
                        isPrime[k] = false;
                    }
        }
}

        if (arraySize > 2)
        {
                    cout << 2 << "\t" << 3 << "\t";//adds 2 and 3 to the output
        }
/*********************************   Output Prime Numbers    *************************/
   for (int x = 2; x <= arraySize; x++)
   {
        if (isPrime[x])
        {
            cout << x << "\t" << flush;
            numberPrimes++;
        }
   }

   cout << "\n\nNumber of Primes: " << numberPrimes << endl;

   return 0;
}

//END OF CODE