2

我今天开始研究 Project Euler 问题，让自己忙于休息。其中一个问题要求所有质数的总和低于 200 万，所以我拼凑了一个埃拉托色尼筛来找出所有这些数字。 

unsigned long i, j, sum = 0, limit = 2000000;

// Allocate an array to store the state of numbers (1 is prime, 0 is not).
int* primes = malloc(limit * sizeof(int));

// Initialize every number as prime.
for (i = 0; i < limit; i++)
    primes[i] = 1;

// Use the sieve to check off values that are not prime.
for (i = 2; i*i < limit; i++)
    if (primes[i] != 0)
        for (j = 2; i*j < limit; j++)
            primes[i*j] = 0;

// Get the sum of all numbers still marked prime.
for (i = 2; i < limit; i++)
    if (primes[i] != 0)
        sum += i;

printf("%d", sum);

这完美地工作了limit大约一百万。此后，它返回随机值（例如，1000000 返回 -1104303641）。我尝试将所有unsigned long变量声明为unsigned long long无济于事。错误似乎发生在最后 4 行，因为primes[]此时只包含 1 和 0。我认为这与正在使用的值的大小有关，任何人都可以提供任何指导吗？

4

2 回答 2

6

Wolfram Alpha 告诉我，小于 500000 的素数之和是9914236195。

该数字不适合 32 位整数，因此您在求和循环期间溢出了一个 int。您可以尝试使用 a uint64_t，但该问题最终会在足够高的限制下再次发生（尽管我怀疑 2000000 的限制会适合）。

于 2012-12-11T04:00:41.637 回答
3

将 %d 更改为 %ld ，您应该得到：

142913828922

这似乎应该是（接近或）正确答案。

..假设您的 long 不是 32 位的。

如果您在 32 位平台上，您将需要某种第三方大型 int 库。

C语言中的大整数？

推荐： http: //gmplib.org/

于 2012-12-11T04:04:25.287 回答