0

我正在做欧拉项目，我遇到了这个问题。我在 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。第二种方法需要很长时间才能获得结果，并且可能需要一整天。第一种方法是使用阿特金的筛子，程序崩溃！

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

4

1 回答 1

2

那么，让我们谈谈这个问题：

整数大小

就像 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;

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

您的快速方法

我还没有完全看完这段代码，因为它看起来不像我记得的 Eratosthenes 筛子，但至少，你的分配会溢出堆栈。

#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. 埃拉托色尼筛是一种更简单的筛。我建议接下来使用它。

  3. 然后尝试实现atkin 的筛子。但是，对于这种规模的问题，完全不需要这种速度的算法。

于 2014-04-09T17:11:51.900 回答