c++ - Eratosthenes 筛法，数组太大以至于内存超出范围

Question

我想获取 2 和 pow(2, 32) 之间的所有质数，但是，由于 pow(2, 32) 太大，我无法声明那个大数组。以下是我的代码

struct prims_n
{
    long long *prim;
    long long  size;
};

struct prims_n get_prim_number(long long number)
{
    long long count = 0;
    struct prims_n result;
    bool* a = new bool[number+1];
    memset(a, 1, number+1);
    for(long long i = 2; i <= sqrt(number); i ++)
    {
        if(a[i])
        {
            for(long long j = 2; j <= number/i; j ++)
            {
                a[i*j] = 0;
            }
        }
    }
    for (long long i = 2; i <= number; i++)
    {
        if (a[i]) count ++;
    }
    result.size = count;
    long long k = 0;
    result.prim = new long long[count];
    for (long long i = 2; i <= number; i++)
    {

        if (a[i] && k < count)
        {
            result.prim[k] = i;
            k ++;
        }
    }
    return result;
}

int main(int argc, char* argv[])
{

    struct  prims_n result = get_prim_number(pow(2, 26));
    cout << "prim numbers:" << result.size 
        << " pow(2, 32)=" <<  pow(2, 32) << endl;
    return 0;
}

我的操作系统是 Windows，IDE 是 Visual Studio 2012。
数字 pow(2, 32) 太大，Sieve of Eratosthenes 计算效率不高。那么，我该怎么办？

Answer 1

简单方法:为 64 位目标构建并安装大量 RAM。

或者您可以通过不为每个数字存储一个 int 而只存储一个位来减少所需的内存。 std::vector<bool>或 std::bitset<N>会是很好用的容器。 bitset需要在编译时知道大小，vector允许它改变。顺便说一句，vector<bool>专门用于优化内存使用。

当然，您并不真的需要存储所有数字 1..N，因为您知道偶数不可能是质数。因此，您可以使用一个数组，例如索引处的元素 i表示信息 if 2*i+1是素数。

其他选项:仅存储质数，然后对于每个要测试的新数，尝试将其除以您已经计算和存储的质数(不是全部，最多为 sqrt())。

或者使用筛子的窗口 View :将已知素数存储在一个容器中，并为整个缓冲区的一部分分配空间。如果缓冲区已完成，则移至下一个窗口。