Sieve of Eratosthenes code problem

[Pauletto]

Good day.

I am new at c++ and while doing an exercise about the Sieve of Eratosthenes i've met a problem. The code is written below. It isn't optimal but it should work (by logic). I can't understand why it doesn't work with number more than 26. I've tried step by step debugging with values' watching but it didnt make it Could someone explain? Thank you for your attention.

#include<iostream>
#include<cmath>
#include<string>
#include<vector>


using namespace std;

int main(){
    vector<double> digits;
    vector<double> primes;
    int m=0;
    cin>>m;
    for (int i=2;i<=m;++i)
        digits.push_back(i);
    int pos=0;
    int halfsize=digits.size()*0.5;
    for (int i=0;i<halfsize;++i){
        pos=i;
        if (digits[i]!=0){
            while (pos<m){
                pos+=digits[i];
                if (digits[pos]!=0) digits[pos]=0;
}
}
}
    for (int i=0;i<m;++i)
        if (digits[i]!=0) primes.push_back(digits[i]);

    for (int i=0;i<primes.size();++i)
        cout<<primes[i]<<"\n";
}

[tipaye]

Please elaborate, what exactly do you mean by "doesn't work"?

[Pauletto]

If the input value is 26 it works very well. But if I input 27 or more it is terminated with message "terminate called after throwing an instance of 'St9bad_alloc'".

[tipaye]

I've tried and failed to reproduce the problem.

From what you've said, it looks like the system failed to allocate memory requested by new. It could be all the calls to push_back is causing the vectors to be re-sized frequently, leading to memory fragmentation. I'm just guessing, but if I'm right, this shouldn't be happening every time you run the code..

[Pauletto]

When I made step by step debugging, the program was terminated at 'while' cycle.

I write my code in Code::Blocks. After the program is terminated i have this text in Debugger window:

"Program received signal SIGTRAP, Trace/breakpoint trap.
In ntdll!RtlDosPathNameToRelativeNtPathName_U_WithStatus () (C:\Windows\system32\ntdll.dll)
#20 0x0042050c in __gnu_cxx::new_allocator<double>::deallocate (this=0x27fed4, __p=0x3712d0) at d:/program files (x86)/codeblocks/mingw/bin/../lib/gcc/mingw32/4.7.1/include/c++/ext/new_allocator.h:100


d:\program files (x86)\codeblocks\mingw\lib\gcc\mingw32\4.7.1\include\c++\ext\new_allocator.h:100:3138:beg:0x42050c
At d:\program files (x86)\codeblocks\mingw\lib\gcc\mingw32\4.7.1\include\c++\ext\new_allocator.h:100
"

[dhayden]

The loop at lines 14 & 15 puts m-1 items into the digits vector. These items have indexes 0 to m-2. So with m=26, the legal indexes are 0-24. Let's add cout << " check digits[" << pos << "]\n"; before line 23 and run the program with input 26:

$ ./foo
26
  check digits[2]
  check digits[4]
  check digits[6]
  check digits[8]
  check digits[10]
  check digits[12]
  check digits[14]
  check digits[16]
  check digits[18]
  check digits[20]
  check digits[22]
  check digits[24]
  check digits[26]
  check digits[4]
  check digits[7]
  check digits[10]
  check digits[13]
  check digits[16]
  check digits[19]
  check digits[22]
  check digits[25]
  check digits[28]
  check digits[8]
  check digits[13]
  check digits[18]
  check digits[23]
  check digits[28]
  check digits[12]
  check digits[19]
  check digits[26]
  check digits[20]
  check digits[31]
  check digits[24]
  check digits[37]
2
3
5
7
11
13
17
19
23

So the problem is that you're accessing the vector out of bounds.

I see two problems here.
Line 21 should be if (pos<digits.size()). You want to go through all the items int the array.
Line 21 & 22: You need to increment the value first, then check it, and if it's okay then set it to zero. To do this you actually have to increment once before entering the loop, and again at the end of each iteration:

        if (digits[i] != 0) {
            pos += digits[i];
            while (pos < digits.size()) {
                if (digits[pos] != 0)
                    digits[pos] = 0;
                pos += digits[i];
            }
        }

[Pauletto]

Thank you very much.

It helped and I understood what I did wrong.