使用阿特金筛法计算200万以下素数之和

Question

我在做 Euler 项目时遇到了这个问题。我在 VS 2013 中运行代码，程序因溢出而崩溃。

这是我的方法:

void problem10()
{
    long long int iter = 2, sum = 0;

    //Sieve of Atkin
    bool isPrime[PRIME_LIMIT+1];

    for (long long int i = 5; i <= PRIME_LIMIT; i++)
    {
        isPrime[i] = false;
    }

    long long int lim = ceil(sqrt(PRIME_LIMIT));

    for (long long int x = 1; x <= lim; x++)
    {
        for (long long int y = 1; y <= lim; y++)
        {
            long long int n = 4 * x*x + y*y;
            if (n <= PRIME_LIMIT && (n % 12 == 1 || n % 12 == 5))
            {
                isPrime[n] = true;
            }

            n = 3 * x*x + y*y;
            if (n <= PRIME_LIMIT && (n % 12 == 7))
            {
                isPrime[n] = true;
            }

            n = 3 * x*x - y*y;
            if (x > y && n < PRIME_LIMIT && n % 12 == 11)
            {
                isPrime[n] = true;
            }
        }
    }

    // eliminate composites by seiving
    for (long long int n = 5; n <= lim; n++)
    {
        if (isPrime[n])
        {
            for (long long int k = n*n; k <= PRIME_LIMIT; k+= k*k)
            {
                isPrime[k] = false;
            }
        }
    }

    for (long long int n = 5; n <= PRIME_LIMIT; n++)
    {
        if (isPrime[n])
        {
            sum += n;
        }
    }
    sum = sum + 2 + 3;
    printf("%lld\n", sum);
    /* //A basic approach -- too slow
    while (iter < PRIME_LIMIT)
    {
        bool isDivisible = false;
        int prime = iter;
        for (int a = 2; a < iter; a++)
        {
            if (prime%a == 0)
            {
                isDivisible = true;
                break;
            }
        }

        if (isDivisible){}
        else
        {
            //printf("prime is: %d\n", prime);
            sum += prime;
        }
        iter++;
    }
    printf("Sum of prime is: %d\n", sum);
    */
}

此方法包括 2 种方法来计算 PRIME_LIMIT 范围内所有素数的和。第二种方法需要很长时间才能得到结果，可能需要一整天。第一种方法是使用阿特金筛法，程序崩溃了!

我的代码有什么错误吗？请帮忙!

Answer 1

那么，让我们来谈谈这个问题:

整数大小

与 Java 非常相似，C 中的整数对其可以容纳的大小有限制。在这里，您选择使用 long long int。幸运的是，对于这个问题，总和将适合该数据类型。对于其他 Project Euler 问题，您将需要使用 BigInt 类。

你缓慢的接近

如果添加一个，慢速方法实际上很好。我们知道，我们需要搜索的除数列表实际上少于 2 ... n 中的所有数字。所以我们可以将您的循环之一更改为:

int max = ciel(sqrt(iter));
for (int a = 2; a < max; a++)
    if (prime % a == 0)
        isDivisible = true;
        break;

如果我们这样做，您的代码将相对快速地完成。

你的快速方法

我还没有完全检查这段代码，因为它看起来不像我记得的埃拉托色尼筛法，但至少，你的分配会溢出堆栈。

#define PRIME_LIMIT 2000000
bool isPrime[PRIME_LIMIT+1];

让我们解决这个问题:

#define PRIME_LIMIT 2000000
static bool isPrime[PRIME_LIMIT+1]

或者:

#define PRIME_LIMIT 2000000
bool *isPrime = calloc(PRIME_LIMIT + 1, sizeof(bool));

建议

我真的建议不要从尝试实现阿特金筛分法开始。如果我要将此作为学习练习来实现，我会按以下顺序进行:

1. 您在上面执行的缓慢方法。在python中，类似的代码解决问题大约需要1分钟。我怀疑 C 可以在大约 10 秒(或更快)内完成。

2. sieve of eratosthenes是一个更简单的筛子来实现。我建议接下来使用它。

3. 然后尝试执行 sieve of atkin .不过，这种速度的算法对于这种规模的问题来说是完全没有必要的。