数组大小限制

Question

我用 c++ 编写了以下代码，它应该打印并计算直到 n 的所有素数。该代码适用于 n<=10000 但不适用于 n>=100000.

#include "iostream"
#include "vector"
using namespace std;
int main(){
    int n,ans=0;
    cin>>n;
    vector <bool> v(n+1,true);
    for(int i=2;i<=n;i++){
        if(v[i]){
            cout<<i<<endl;
            ans++;
            for(int j=i*i;j<=n;j+=i)
                v[j]=false;
        }
    }
    cout<<endl<<ans;
    return 0;
}

请说明原因。谢谢。

Answer 1

在您的内心看来，j=i*i 将在 46341 左右溢出一个 32 位有符号整数。最简单的解决方法是对 j 使用 long long 并强制转换 i 乘法前正确。

因此，将内部循环更改为

for (auto j = static_cast<long long>(i) * i; j <= n; j += i)

应该就是这样了。

作为旁注，请不要 #include 标准 headers 加双引号；更喜欢 <vector> 和 <iostream>.

更新：作为做同样事情的更稳健的方式（并且仍然使用大致相同的代码），我建议如下：

#include <iostream>
#include <vector>
using namespace std;
int main(){
    size_t n, ans = 0; // A) Switch to size_t, which can accommodate the largest
                       //    size of a vector; if your number is larger, then we
                       //    can't make an array for it... 
    cin >> n;
    vector<bool> v (n, true); // B) Remove the chance of overflow; indices are
                              //    now shifted by one
    for(size_t i = 2; i <= n; i++) {
        if (v[i - 1]) {
            cout << i << endl;
            ans++;
            if (n / i >= i) { // C) Check for possibility of overflow in `i*i`
                
                // D) Switch j to correct type
                // E) Check if `j+=i` overflowed
                for (size_t j = i * i; j <= n && j > i; j += i)
                    v[j - 1] = false;
            }
        }
    }
    cout << endl << ans;
    return 0;
}

真正重要的变化是 A、C 和 D。另外两个 B 和 E 是完全正确所必需的，但只有当您的系统中有足够的实际内存来几乎溢出 size_t（否则，vector 的构造函数会抛出。）这完全可能在 32 位系统上发生，但目前在 64 位构建上是不可能的。

另请注意，A、B 和 D“基本上”是免费的 (perf-wise)，但 C 和 E 确实对运行时间有一些影响（尽管可能很小；E 是更麻烦。)

数组大小限制

Limit on array size

c++

memory