Mathematicians have been coming up with different ways of finding primes for thousands of years and one of the simplest and accurate ways of doing so is surprisingly ancient. The sieve of Eratosthenes was invented over 2000 years ago by Eratosthenes of Cyrene and is still used today in mathematics as one of the most efficient ways of finding primes. In this article we’ll going through an easy way of implementing this sieve using C++.
Libraries and Function Declarations
For this program you’ll need two libraries, iostream for the “cout” and “cin” objects and math.h for a function that calculates square roots.
#include <iostream> #include <math.h>
Once you’ve included the needed libraries you should declare a void function called sieve. This function should take two arguments, an int variable called limit and a Boolean array called primes.
void sieve(int limit, int primes[]);
The Sieve Function
When you define your sieve function the first thing you should do inside it is create two int variables called i and j.
void sieve(int limit, int primes[])
{
int i;
int prime;
After this create a for loop which iterates through the limit variable. Inside this for loop you should be setting every single position of the prime array to true, later on in we’ll be setting every position in the array that is not a prime equal to false.
for (i = 0;i<limit;i++)
{
primes[i] = true;
}
Before continuing you need to manually set both 0 and 1 to false since these two numbers are not prime and also not included within the prime sieve.
primes[0] = false,primes[1] = false;
Next create another for statement that iterates through the square root of limit. Inside that loop create another for loop, this one will go through and mark every position in the array that is not a prime as false. It does this by multiplying “i” by itself each iteration and setting that number equal to “prime” and then adds “i” to “prime”.
for (i = 2;i<sqrt(limit);i++)
{
for (prime = i * i;prime<limit;prime+=i)
{
primes[prime] = false;
}
}
The Main Function
Start your “int main()” function off by declaring an int variable called limit and getting its value from the user. This is the upper limit on how many primes your calculator will output, so for example if the user inputs 49 then the program will only calculate the primes up to but not including 49.
int main()
{
int limit;
std::cout << "Enter Prime Limit: "; std::cin >> limit;
Next declare a boolean array called “v” with a number of positions equal to “limit”. After that call the sieve function, using “limit” and “v” for its two arguments respectively.
bool numbers[limit]; sieve(limit, numbers);
After the sieve function has been called create a for statement which iterates through “limit”. Inside this statement check if the current position is true or false, if it’s true print the position to the screen.
for (i = 0;i<limit;i++)
{
if (v[i] == true)
{
std::cout << (i) << std::endl;
}
}
This implementation of the sieve while not the best or most efficient is fairly simple in its design. The sieve itself should theoretically be able to find any prime but you’ll quickly discover that the program cannot be pushed very far beyond one million due to memory issues.
Further Suggestions
If you want add to your prime sieve program try writing all of the primes to a text file so the user can view them all after the program has finished running. You can also try implementing one of the more complex sieves such as the sieve of Sundaram or the Sieve of Atkin.
Good Luck!
Download the source code here.
If you have any questions or comments email them to me at nick@crumbsofcode.com
