CODEWITHSUNDEEP
c++loopssieve-of-eratosthenes
Blessing Hwacha
Blessing Hwacha

Reputation: 15

Why is my sieve of Eratosthenes code looping infinitely. I have tested with a few numbers

I am trying to implement The sieve of Eratosthenes algorithm in C++, from the pseudo code below:

Input: an integer n > 1.

Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n: if A[i] is true: for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n: A[j] := false.

Output: all i such that A[i] is true.

However my code loops infinitely in the last for loop and I can't figure out why.

void primes(int n)
{
    bool numArr[n];
    for (int a=2;a<n;a++)
       {
           numArr[a]=true;
       }
    int   k,j, m = int(sqrt(n));
    for(int i=2;i<m;i++)

    {
        k=0;
        if(numArr[i]==true)
        {
            for(j=i^2;j<n;j+(k*i))
            {
                numArr[j]=false;
                k++;
            }

        }

    }

    for(int j=1;j<n;j++)
    {
        if(numArr[j]==true)
        {
            cout<<numArr[j]<<endl;
        }
    }

}

Upvotes: 0

Views: 48

Answers (1)

Blaze
Blaze

Reputation: 16876

First of all, there are no VLAs in C++. Some compilers will tolerate them nevertheless, others won't. For a portable solution, std::vector works very well. Replace your VLA with this:

std::vector<bool> numArr(n);

You can even put the initialization into this. No need for that loop that sets everything to true, just change the numArr(n) to numArr(n, true) and it's all done for you.

Your main problem is here, however:

for(j=i^2;j<n;j+(k*i))

j=i^2 doesn't do what you think it does and your increment of j+(k*i) doesn't increase anything. Actually, the k part makes no sense. Do this instead:

for (j = i*i; j < n; j += i)

Your print of cout<<numArr[j]<<endl; is wrong, too. numArr[j] is a bool, so that's going to print a 1 every time. Surely you wanted to print j instead of numArr[j].

And while it's not a problem, you don't have to write if (numArr[i] == true). Just do if (numArr[i]) instead. numArr[i] is already a bool.

Upvotes: 2

Related Questions