我正在从 Robert Sedgewick 的《C++ 算法》中学习 C++。现在我正在研究埃拉托色尼筛法,其中用户指定了最大素数的上限。当我运行最大 46349 的代码时,它会运行并打印出最大 46349 的所有素数,但是当我运行最大 46350 的代码时,会发生段错误。谁能帮忙解释下原因?
./sieve.exe 46349
2 3 5 7 11 13 17 19 23 29 31 ...
./sieve.exe 46350
Segmentation fault: 11
代码:
#include<iostream>
using namespace std;
static const int N = 1000;
int main(int argc, char *argv[]) {
int i, M;
//parse argument as integer
if( argv[1] ) {
M = atoi(argv[1]);
}
if( not M ) {
M = N;
}
//allocate memory to the array
int *a = new int[M];
//are we out of memory?
if( a == 0 ) {
cout << "Out of memory" << endl;
return 0;
}
// set every number to be prime
for( i = 2; i < M; i++) {
a[i] = 1;
}
for( i = 2; i < M; i++ ) {
//if i is prime
if( a[i] ) {
//mark its multiples as non-prime
for( int j = i; j * i < M; j++ ) {
a[i * j] = 0;
}
}
}
for( i = 2; i < M; i++ ) {
if( a[i] ) {
cout << " " << i;
}
}
cout << endl;
return 0;
}
最佳答案
这里有整数溢出:
for( int j = i; j * i < M; j++ ) {
a[i * j] = 0;
}
46349 * 46349
不适合 int
。
在我的机器上,将 j
的类型更改为 long
可以为更大的输入运行程序:
for( long j = i; j * i < M; j++ ) {
根据您的编译器和体系结构,您可能必须使用 long long
才能获得相同的效果。
关于C++ Array Allocation Segmental Fault 11 新手,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15177018/