value 需要 1000000000 字节，大于 max-value-size

Question

我在 spoj.com

遇到了这个问题

http://www.spoj.com/problems/PRIME1/

阅读了一些有关素数生成算法的内容后，我发现 "Sieve of Atkins" 是最快的素数生成算法。我已经在本教程的帮助下部分实现了该算法 http://www.geeksforgeeks.org/sieve-of-atkin/

当我运行代码时，它给了我分段错误。调试后我才知道这段代码不是最优的，它使用了更多的内存和存储空间。谁能告诉我如何优化程序。这是我的代码片段。是的，它是不完整的。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int sieveOfAtkin(long int limit)
{
    // if limit is either 2 or 3, print them
    if (limit >= 2)
    {
        cout << 2 << endl;
    }

    if (limit >= 3)
    {
        cout << 3 << endl;
    }


    bool sieve[limit];
    for (long int i=0; i<=limit; i++)
        sieve[i] = false;

    for (long int x=1; x<limit; x++)
    {
        for (long int y=1; y<limit; y++)
        {

            long int n = (4*x*x) + (y*y);
            if (n<=limit && (n%12==1 || n%12==5))
                sieve[n] ^= true;

            n = (3*x*x) + (y*y);
            if (n<=limit && (n%12==7))
                sieve[n] ^= true;

            n = (3*x*x) - (y*y);
            if (x>y && n<=limit && (n%12==11))
                sieve[n] ^= true;
        }
    }

    for (long int r=5; r*r<limit; r++)
    {
        if(sieve[r])
        {
            for(long int i=r*r; i<limit; i+=r*r)
                sieve[r] = false;
        }
    }

    for (long int i=5; i<limit; i++)
        if(sieve[i])
            cout << i << endl; 

    return 0;
}

int main(void)
{
    long int x;
    cin >> x;
    sieveOfAtkin(x);
    return 0;
}

Answer 1

首先，阿特金筛法比埃拉托色尼筛法更快是网络神话。阿特金筛法在某些约束下更快，但埃拉托色尼筛法通常更快，并且是实际使用它来研究素数的数学家选择的筛法。

其次，当筛子变得太大而无法放入内存时，您可以分段筛子。有关详细信息，请参阅 this answer。

value 需要 1000000000 字节，大于 max-value-size

value requires 1000000000 bytes, which is more than max-value-size

c++

algorithm

primes

sieve

sieve-of-atkin