数组大小的限制

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标准标题；优选CCD_ 6和CCD_。

UPDATE：作为一种更稳健的方式来做同样的事情(并且仍然使用大致相同的代码(，我建议如下：

#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的ctor会抛出。(这可能在32位系统上完全可行，但目前在64位构建中是不可能的。

还要注意，A、B和D是"；基本上"；免费(性能方面(，但C和E确实对运行时间有一些影响(尽管可能很小；E更繁重。(