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.

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 dont know much about c++.

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

Am i doing something wrong? Also any critiscism is greatly apreciated.

Os: Windows 7

Answer 1

From Algorithms and Data Structures:

void runEratosthenesSieve(int upperBound) {
      int upperBoundSquareRoot = (int)sqrt((double)upperBound);
      bool *isComposite = new bool[upperBound + 1];
      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
      for (int m = 2; m <= upperBoundSquareRoot; m++) {
            if (!isComposite[m]) {
                  cout << m << " ";
                  for (int k = m * m; k <= upperBound; k += m)
                        isComposite[k] = true;
            }
      }
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)
            if (!isComposite[m])
                  cout << m << " ";
      delete [] isComposite;
}

Answer 2

In the code fragment below, the numbers are filtered before they are inserted into the vector. The divisors come from the vector.

I'm also passing the vector by reference. This means that the huge vector won't be copied from the function to the caller. (Large chunks of memory take long times to copy)

vector<unsigned int> primes;

void calc_primes(vector<unsigned int>& primes, const unsigned int MAX)
{
  // If MAX is less than 2, return an empty vector
  //    because 2 is the first prime and can't be placed in the vector.
  if (MAX < 2)
      return;

  // 2 is the initial and unusual prime, so enter it without calculations.
  primes.push_back(2);

  for (unsigned int number = 3;
       number < MAX;
       number += 2)
  {
    bool  is_prime(true);
    for (unsigned int index = 0;
         index < primes.size();
         ++index)
    {
       if ((number % primes[k]) == 0)
       {
         is_prime = false;
         break;
       }
    }
    if (is_prime)
    {
      primes.push_back(number);
    }
  return;
}

This not the most efficient algorithm, but it follows the Sieve algorithm.

Answer 3

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"));

}

Answer 4

Interestingly, nobody seems to have answered your question about the output problem. I don't see anything in the code that should effect the output depending on the value of max.

For what it's worth, on my Mac, I get all the output. It's wrong of course, since the algorithm isn't correct, but I do get all the output. You don't mention what platform you're running on, which might be useful if you continue to have output problems.

---

Here's a version of your code, minimally modified to follow the actual Sieve algorithm.

#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;

    // fill vector with candidates
    for(int i = 2; i < max; i++)
    {
     primes.push_back(i);
    }

    // for each value in the vector...
    for(int i = 0; i < primes.size(); i++)
    {
     //get the value
     int v = primes[i];

     if (v!=0) {
      //remove all multiples of the value
      int x = i+v;
      while(x < primes.size()) {
       primes[x]=0;
       x = x+v;
      }
     }
    }
    return primes;
}

Answer 5

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.push_back(i);   // you'll learn more efficient ways to handle this later

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