This program uses pointer manipulations and iterative looping to find all of the
prime numbers within a specified range by following the Sieve of Eratosthenes.
//Sieve of Eratosthenes by Jack P. Oakley
//This program finds all of the prime numbers between two specified numbers as
//referenced from https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>
using namespace std;
#include <math.h>
int getUpBound(void);
int getLowBound(int upBound);
char askRepeat(void);
int *createArray(int size);
int searchArray(int *numList, int size);
void remFactors(int *numList, int size, int factor);
void zeroToOne(int *numList, int size);
int *getCircled(int *numList, int size, int &newSize);
void displayPrimes(int *primeList, int primeSize, int lowerBound);
void holdScreen(void);
/*******************************************************************************
* main function: *
* PURPOSE: Drives the program *
* IN: none *
* OUT: none *
*******************************************************************************/
void main(void)
{
int upperBound, lowerBound, currIndex, primeSize;
int *arrayBegin, *primeNums;
char repeat;
cout << "Sieve of Eratosthenes" << endl << endl;
do
{
do
{
upperBound = getUpBound();
lowerBound = getLowBound(upperBound);
if (lowerBound >= upperBound)
{
cout << "The lower boundary is greater than your high boundary, "
<< "please enter a number " << endl << "lower than or equal to "
<< upperBound << "." << endl << endl;
}
} while (lowerBound >= upperBound);
++upperBound;
arrayBegin = createArray(upperBound);
do
{
currIndex = searchArray(arrayBegin, upperBound);
if (currIndex != -1)
{
remFactors(arrayBegin, upperBound, currIndex);
}
} while (currIndex <= sqrt(upperBound));
zeroToOne(arrayBegin, upperBound);
primeNums = getCircled(arrayBegin, upperBound, primeSize);
displayPrimes(primeNums, primeSize, lowerBound);
repeat = askRepeat();
} while (repeat == 'Y' || repeat == 'y');
} //End main()
/*******************************************************************************
* getUpBound function: *
* PURPOSE: Obtain upper boundary from user *
* IN: none *
* OUT: int representing upper boundary *
*******************************************************************************/
int getUpBound(void)
{
int boundary;
do
{
cout << "Please enter the high boundary of the prime numbers you want: ";
cin >> boundary;
if (boundary <= 0)
{
cout << "That was not positive, please enter a positive number." <<
endl << endl;
}
} while (boundary <= 0);
return boundary;
} //End getUpBound()
/*******************************************************************************
* getLowBound function: *
* PURPOSE: Obtain lower boundary from user *
* IN: int for upper boundary *
* OUT: int representing lower boundary *
*******************************************************************************/
int getLowBound(int upBound)
{
int boundary;
do
{
cout << "Please enter the low boundary of the prime numbers you want: ";
cin >> boundary;
if (boundary <= 0)
{
cout << "That was not positive, please enter a positive number." <<
endl << endl;
}
} while (boundary <= 0);
return boundary;
} //End getLowBound()
/*******************************************************************************
* askRepeat function: *
* PURPOSE: Ask user if they want to repeat the program *
* IN: none *
* OUT: char with user's choice (y/n) *
*******************************************************************************/
char askRepeat(void)
{
char repeat;
do
{
cout << endl << "Do you want to do it again? (y/n) ";
cin >> repeat;
if (repeat != 'Y' && repeat != 'y' && repeat != 'n' && repeat != 'N')
{
cout << "Please enter an 'n' or a 'y'." << endl << endl;
}
} while (repeat != 'Y' && repeat != 'y' && repeat != 'n' && repeat != 'N');
return repeat;
} //End askRepeat()
/*******************************************************************************
* createArray function: *
* PURPOSE: Create an array of given size *
* IN: int for array size *
* OUT: int array of specified size, filled with 0s *
*******************************************************************************/
int *createArray(int size)
{
int *numbers = new int[size*2];
int *begin = numbers;
int *end = begin + size;
*(numbers + 1) = *numbers = -1;
numbers += 2;
while (numbers < end)
{
*numbers = 0;
++numbers;
}
return begin;
} //End createArray()
/*******************************************************************************
* searchArray function: *
* PURPOSE: Finds and returns the first index containing a 0 *
* IN: int array, int array size *
* OUT: int representing first index containing a 0 *
*******************************************************************************/
int searchArray(int *numList, int size)
{
int *begin = numList;
int *end = begin + size;
int toReturn = -1;
while (numList < end)
{
if (*numList == 0)
{
toReturn = (numList - begin);
numList = begin;
return toReturn;
}
++numList;
}
numList = begin;
return toReturn;
} //End searchArray()
/*******************************************************************************
* remFactors function: *
* PURPOSE: Fills in remaining factors with -1 (crosses them out as non-primes) *
* IN: int array, int array size, int current factor *
* OUT: none *
*******************************************************************************/
void remFactors(int *numList, int size, int factor)
{
int *end = numList + size;
int *begin = numList;
numList = numList + factor;
*numList = 1;
while (numList < end)
{
numList = numList + factor;
*numList = -1;
}
numList = begin;
} //End remFactors()
/*******************************************************************************
* zeroToOne function: *
* PURPOSE: Fill remaining empty cells with 1s as primes *
* IN: int array, int array size *
* OUT: none *
*******************************************************************************/
void zeroToOne(int *numList, int size)
{
int *end = numList + size;
int *begin = numList;
while (numList < end)
{
if (*numList == 0)
{
*numList = 1;
}
++numList;
}
numList = begin;
} //End zeroToOne()
/*******************************************************************************
* getCircled function: *
* PURPOSE: Obtain new array containing the values from indices circled (1s) *
* IN: int array with circled indices, int array size, int reference param to *
* hold new array size *
* OUT: int array of only prime numbers *
*******************************************************************************/
int *getCircled(int *numList, int size, int &newSize)
{
int *begin = numList;
int *end = begin + size;
int *circledList;
int *circledBegin;
newSize = 0;
while (numList < end)
{
if (*numList == 1)
{
++newSize;
}
++numList;
}
numList = begin;
circledList = createArray(newSize);
circledBegin = circledList;
while (numList < end)
{
if (*numList == 1)
{
*circledList = (numList - begin);
++circledList;
}
++numList;
}
numList = begin;
return circledBegin;
} //End getCircled()
/*******************************************************************************
* displayPrimes function: *
* PURPOSE: Print resulting primes to console *
* IN: int array of all primes, int array size, int lowerbound of what is to be *
* displayed *
* OUT: none *
*******************************************************************************/
void displayPrimes(int *primeList, int primeSize, int lowerBound)
{
int *end = primeList + primeSize;
int *begin = primeList;
int count = 1;
cout << endl;
while (primeList < end)
{
if (*primeList >= lowerBound)
{
cout << *primeList << "\t";
if (count % 10 == 0)
{
cout << endl;
}
if (count % 100 == 0)
{
holdScreen();
}
++count;
}
++primeList;
}
cout << endl;
primeList = begin;
} //End displayPrimes
/*******************************************************************************
* holdScreen function: *
* PURPOSE: hold screen for user if range is too large to fit in one console *
* IN: none *
* OUT: none *
*******************************************************************************/
void holdScreen(void)
{
char entry;
cout << "Enter any letter and press enter to continue: ";
cin >> entry;
cout << endl;
} //End holdScreen()