C++ sieve of Eratosthenes with array [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I'd like to code the famous Sieve of Eratosthenes in C++ using just array as it would be a set where I can delete some elements on the way to find out primes numbers. I don't want to use STL (vector, set)... Just array! How can I realize it?

I try to explain why I don't want to use STL set operator: I'm learning C++ from the very beginning and I think STL is of course useful for programmers but built on standard library, so I'd like to use former operators and commands. I know that everything could be easier with STL.

Answer 1

The key to the sieve of Eratosthenes's efficiency is that it does not, repeat not, delete ⁄ remove ⁄ throw away ⁄ etc. the composites as it enumerates them, but instead just marks them as such.

Keeping all the numbers preserves our ability to use a number's value as its address in this array and thus directly address it: array[n]. This is what makes the sieve's enumeration and marking off of each prime's multiples efficient, when implemented on modern random-access memory computers (just as with the integer sorting algorithms).

To make that array simulate a set, we give each entry two possible values, flags: on and off, prime or composite, 1 or 0. Yes, we actually only need one bit, not byte, to represent each number in the sieve array, provided we do not remove any of them while working on it.

And btw, vector<bool> is automatically packed, representing bools by bits. Very convenient.

Answer 2

From Algorithms and Data Structures

#include<iostream>
#include<cmath>
#include<cstring>

using namespace std;

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


int main()
{
 runEratosthenesSieve(1000);
}

You don't want to use STL, but that's not a good idea

STL makes life much simpler.

Still consider this implementation using std::map

int  max = 100;
S sieve;

for(int it=2;it < max;++it)
    sieve.insert(it);

for(S::iterator it = sieve.begin();it != sieve.end();++it)
{
    int  prime   = *it;
    S::iterator x = it;
    ++x;
    while(x != sieve.end())
        if (((*x) % prime) == 0)
            sieve.erase(x++);
        else
            ++x;
}

for(S::iterator it = sieve.begin();it != sieve.end();++it)
 std::cout<<*it<<std::endl;