C :分割故障(核心倾倒)问题

Question

c 中的eratosthenes的筛子实现：

当我运行C 程序时，我会得到

"分割故障(核心倾倒("

它编译而没有任何错误。

在此程序中，我试图在两个数字A和B。

之间打印所有质量数字

#include <iostream>
#include <string.h>
#define MAX 1000000
using namespace std;
// Print all primes s.t. a <= prime <= b
int main()
{
    int t; // no of test cases
    cin>>t;
    bool prime[MAX + 1];    // a[i] = true for i = prime
    long int count_primes_lte_me[MAX + 1]; // a[i] = Count ( primes ) <= i
    long int counter_of_visited_primes;
    prime[0] = prime[1] = false;
    for(int i = 2 ; i <= MAX ; i++)
    {
        if(prime[i] == true)
            count_primes_lte_me[i] = ++counter_of_visited_primes;
        for(int j = i*i ; j <= MAX ; j += i)  // sieve of eratosthenes
            prime[j] = false;
    }
    long int a , b;
    while(t--)
    {
        cin>>a>>b;
        cout<<count_primes_lte_me[b] - count_primes_lte_me[a - 1]<<endl;
    }
    return 0;
}

Answer 1

尝试MAX的值较小。在堆栈上分配如此大的阵列会产生(初始(问题。然后替换为动态分配：

bool *prime = new bool[MAX+1];
if (prime==nullptr) // error
...
delete [] prime;

您也可以使用静态分配(将变量定义为全局(。

最好的可能是使用一些适当的容器，例如bitset。

谨慎 i*i可能会溢出，因此可能出现其他问题...

Answer 2

i * i将在您的内部循环中溢出i <= MAX。由于j负，这可能会导致segfault。使用较大的整数类型：long long j = (long long)i * i。

为了正确性，您需要将prime数组初始化为true，将计数数组和0值初始化。

Answer 3

您的最大为一百万...我试图减少它，没有错误，但仍然没有任何作用...尝试此

/************************************
***Array names as pointers***********
************************************/
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
    const int MAX = 10000;
    long prime[MAX] = { 2, 3, 5 };
    long trial = 5;
    int count = 3;
    int found = 0;
    do
    {
        trial += 2;
        found = 0;
        for (int i = 0; i < count; i++)
        {
            found = (trial % *(prime + i)/* prime[i] */) == 0;
            if (found)
                break;
        }
        if (found == 0)
            *(prime + count++)/* prime[count++] */ = trial;
    } while (count < MAX);
    for (int i = 0; i < MAX; i++)
    {
        if (i % 5 == 0)
            cout << endl;
        cout << setw(10) << *(prime + i)/* prime[i] */;
    }
    cout << endl;
    return 0;
}