c - 输入太大时算法返回垃圾？

Question

我今天开始研究 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 大约 50 万。此后，它返回随机值(例如，1000000 返回 -1104303641)。我已经尝试将所有 unsigned long 变量声明为 unsigned long long 但无济于事。错误似乎发生在最后 4 行，因为 primes[] 在那一点只包含 1 和 0。我认为这与正在处理的值的大小有关，任何人都可以提供任何指导吗？

Answer 1

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

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