Problem with dynamic arrays (I suppose) for numbers from 200-CodePudding

I am writing an algorithm which outputs all prime numbers in range [3; n]. Take a look at my code and I will explain the problem:

#include <iostream>
using namespace std;

int main()
{
    int n;

    cout << "Enter the value of n:" << endl;
    cin >> n;

    int k = (n - 2) / 2   1;

    bool* nums = new bool[k];
    for (int i = 0; i < k; i  ) nums[i] = true; 

    for (int i = 1; i < k; i  )
    {
        int j = i;

        while (i   j   2 * i * j <= k)
        {
            nums[i   j   2 * i * j] = false;
            j  ;
        }
    }

    for (int i = 1; i < k; i  )
    {
        if (nums[i])
        {
            cout << 2 * i   1 << endl;
        }
    }

    delete[]nums;
    nums = NULL;

    system("pause>0");
}

For n < 200 everything works well. But for n >= 200 I get the error:

Debug Error!
<...>
HEAP CORRUPTION DETECTED: after Normal block (#764) at
0x008655A0.
CRT detected that the application wrote to memory after end of heap buffer.

How to fix it? I am sure that this problem is surrounding dynamic array nums.

CodePudding user response：

The array is allocated to k elements. Arrays are 0-indexed, so valid indexes are [0..k-1], thus k itself is not a valid index. As such, using >= k in the inner while loop will allow it to go out of bounds on the last iteration, writing data to surrounding memory. You need to use < k instead.

CodePudding user response：

This loop

    while (i   j   2 * i * j <= k)
    {
        nums[i   j   2 * i * j] = false;
        j  ;
    }

might access nums out of bounds in the last iteration, when i j 2*i*j == k, because the last valid index is k-1.

Out of bounds access is undefined behavior in C , hence your code might appear to work for n < 200. Also, the index, i j 2*i*j, increases by 1 2*i in each iteration, hence there are values for n where the out-of-bounds access does not occur (eg when k is prime).

To make the condition a little less error prone, you can consider to rewrite the loop like this:

 for (int m = ... ; m < k; m = 1 2*i) {
     nums[m] = false;
 }