c++ - 筛分高达20亿个导致段错误

我正在使用此程序检查是否为素数。

使用算法-筛子:

#include<bits/stdc++.h>
//#define _max    2000000001
#define _max    20000001
using namespace std;
bool sieve[_max];
void init()
{
    memset(sieve,true,sizeof(sieve));
    sieve[0]=sieve[1]=false;
    for(int i=2;i<_max;i+=2)
    {
        sieve[i]=false;
    }
}
void go_sieve(int n)
{
    n++;
    for(int i=3;i<n;i+=2)
    {
        if(sieve[i]==false)
            continue;
        for(int j=2*i;j<n;j+=i)
            sieve[j]=false;
    }
}
void print(int n)
{
    n++;
    printf("-------------\n");
    for(int i=0;i<n;i++)
    {
        if(sieve[i])
            cout << i << " ";
    }
    printf("\n-------------\n");
}
int main()
{
    init();
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        go_sieve(x);
        //print(x);
        if(sieve[x])
            printf("Prime\n");
        else
            printf("Not prime\n");
    }
    return 0;
}

现在它可以在2e7上正常运行，但是非常平稳，但是我想在2e9上进行检查，如果我将_max更改为2000000001，它会给我segmentation error并退出并显示错误代码。

如何解决此问题？

我用set尝试了一种新方法:

#include<bits/stdc++.h>
//#define _max    200001
//#define _max    20000001
#define _max    2000000001
using namespace std;
set<int>prime;
set<int>nprime;
void init()
{
    prime.insert(2);
}
void go_sieve()
{
    for(int i=3;i<_max;i+=2)
    {
        if(prime.find(i)==prime.end() && nprime.find(i)==nprime.end())
        {
            prime.insert(i);
            //cout << i << endl;
            for(int j=2*i;j<_max;j+=i)
                nprime.insert(j);
        }
        if(nprime.find(i)!=nprime.end())
            nprime.erase(nprime.find(i));
    }
}
void print()
{
    set<int> ::iterator itt;
    printf("-------------\n");
    for(itt=prime.begin();itt!=prime.end();itt++)
    {
        cout << *itt << " ";
    }
    printf("\n-------------\n");
}
int main()
{
    init();
    go_sieve();
    //print();
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        if(prime.find(x)!=prime.end())
            printf("Prime\n");
        else
            printf("Not prime\n");
    }
    return 0;
}

目标是在512MB〜1GB内存中执行它。

最佳答案

如果要枚举大范围的质数，则应使用segmented Sieve of Eratosthenes；它将更快(由于缓存效果)并且使用更少的内存。

如果只想确定一个数是质数还是几个数，那么筛分是一种可怕的方法。仅当您对整个数字范围感兴趣时才应使用筛分。对于不超过10亿的n，审判部门很简单，而且可能足够快。对于更大的数字，Miller-Rabin检验或Baillie-Wagstaff检验可能更好。