c++ - 为什么大数输入会导致此代码计算 primeCounting 时产生运行时错误？

Question

任务是计算输入参数 N 以下的素数个数。 我正在用从小到大的不同输入数字测试这段代码。很奇怪，如果输入值大于和等于 46342，我只会遇到运行时错误。如果输入值小于 46342，代码运行完美，没有任何运行时错误。

int countPrimes(int n) {
    if (n <= 2) return 0;
    vector<bool> array(n,true);
    int cnt = 0;
    for (int i = 2 ; i < n ; i++)
    {
        for (int j = i ; i * j < n ; j++)
        {

            int product = i * j;
            if (array[product])
            {
                array[product] = false;
                cnt++;
            }
        }
    }
    return n - 2 - cnt;
}

如果输入大于等于 46342，我将看到“运行时错误 "，如果输入小于 46342，代码运行正常，结果正确。

Answer 1

这个:

int product = i * j;

将溢出，使 product 等于负数。

然后，您将尝试使用负索引访问array(实际上是一个 vector ，因此将其命名为array 不是一个好的选择)，这将使你的程序崩溃了。

---

您需要使用可以支持更大数值的类型。现在您使用了 int ( C++ Integer Limits )。将 unsigned int 用于 n、i、j 和 product。