# Sieve of Eratosthenes algorithm

### Question

I am currently reading "Programming: Principles and Practice Using C++", in Chapter 4 there is an exercise in which:

I need to make a program to calculate prime numbers between 1 and 100 using the Sieve of Eratosthenes algorithm.

This is the program I came up with:

``````#include <vector>
#include <iostream>

using namespace std;

//finds prime numbers using Sieve of Eratosthenes algorithm
vector<int> calc_primes(const int max);

int main()
{
const int max = 100;

vector<int> primes = calc_primes(max);

for(int i = 0; i < primes.size(); i++)
{
if(primes[i] != 0)
cout<<primes[i]<<endl;
}

return 0;
}

vector<int> calc_primes(const int max)
{
vector<int> primes;

for(int i = 2; i < max; i++)
{
primes.push_back(i);
}

for(int i = 0; i < primes.size(); i++)
{
if(!(primes[i] % 2) && primes[i] != 2)
primes[i] = 0;
else if(!(primes[i] % 3) && primes[i] != 3)
primes[i]= 0;
else if(!(primes[i] % 5) && primes[i] != 5)
primes[i]= 0;
else if(!(primes[i] % 7) && primes[i] != 7)
primes[i]= 0;
}

return primes;
}
``````

Not the best or fastest, but I am still early in the book and don't know much about C++.

Now the problem, until `max` is not bigger than `500` all the values print on the console, if `max > 500` not everything gets printed.

Am I doing something wrong?

P.S.: Also any constructive criticism would be greatly appreciated.

1
5
2/16/2016 6:34:40 PM

I have no idea why you're not getting all the output, as it looks like you should get everything. What output are you missing?

The sieve is implemented wrongly. Something like

``````vector<int> sieve;
vector<int> primes;

for (int i = 1; i < max + 1; ++i)
sieve[0]=0;
for (int i = 2; i < max + 1; ++i) {   // there are lots of brace styles, this is mine
if (sieve[i-1] != 0) {
primes.push_back(sieve[i-1]);
for (int j = 2 * sieve[i-1]; j < max + 1; j += sieve[i-1]) {
sieve[j-1] = 0;
}
}
}
``````

would implement the sieve. (Code above written off the top of my head; not guaranteed to work or even compile. I don't think it's got anything not covered by the end of chapter 4.)

Return `primes` as usual, and print out the entire contents.

5
9/2/2012 7:13:25 PM

Think of the sieve as a set.
Go through the set in order. For each value in thesive remove all numbers that are divisable by it.

``````#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>

typedef std::set<int>   Sieve;

int main()
{
static int const max = 100;

Sieve   sieve;

for(int loop=2;loop < max;++loop)
{
sieve.insert(loop);
}

// A set is ordered.
// So going from beginning to end will give all the values in order.
for(Sieve::iterator loop = sieve.begin();loop != sieve.end();++loop)
{
// prime is the next item in the set
// It has not been deleted so it must be prime.
int             prime   = *loop;

// deleter will iterate over all the items from
// here to the end of the sieve and remove any
// that are divisable be this prime.
Sieve::iterator deleter = loop;
++deleter;

while(deleter != sieve.end())
{
if (((*deleter) % prime) == 0)
{
// If it is exactly divasable then it is not a prime
// So delete it from the sieve. Note the use of post
// increment here. This increments deleter but returns
// the old value to be used in the erase method.
sieve.erase(deleter++);
}
else
{
// Otherwise just increment the deleter.
++deleter;
}
}
}

// This copies all the values left in the sieve to the output.
// i.e. It prints all the primes.
std::copy(sieve.begin(),sieve.end(),std::ostream_iterator<int>(std::cout,"\n"));

}
``````