Euler项目问题#10

Question

我读过关于求解欧拉计划的第十个问题的其他解决方案(找到2,000,000以下的所有素数之和)，但我想用埃拉托斯提尼筛方法自己尝试一下。它运行得很快，它似乎适用于我所有的测试增量(低于10，前1000个素数)，但它似乎不适用于整个200万范围的测试。我想知道是否有人能帮助我指出代码中的问题。我知道这不是最漂亮/最有效的代码，非常抱歉。

#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    // upper limit & sum
    int sum = 0;
    int upLimit = 2000000;

    // array of isPrime check for integers
    bool isPrime[upLimit+1];

    // initialize
    for (int i=2; i <= upLimit; i++) {
        isPrime[i] = true;
    }

    for (int i=2; i<=upLimit; i++) {
        if (isPrime[i]) {
            // add to sum
            sum += i;

            // mark all multiples
            int j = i;
            while (j <= upLimit) {
                isPrime[j] = false;
                j += i;
            }
        }
    }
    cout << sum << endl;
}

Answer 1

在添加之前，您需要检查溢出。

for (int i=2; i<=upLimit; i++) {
    if (isPrime[i]) {
        // Check for overflow
        if (std::numeric_limits<decltype(sum)>::max() - sum <= i) {
            std::cerr << "Overflow" << std::endl;
            return 1;
        }

        // add to sum
        sum += i;
        …

由于int只能保存高达32767的值，所以您会发现您应该为sum使用一个long long。

Answer 2

问题是溢出，可以通过更改代码中的某些类型来解决这个问题(我将假设i是在这里预先声明的)：

int sum = 0;
int upLimit = 2000000;
int i = 2;
int j = i;

虽然int通常是32位整数，但这并不是必需的。我们非常关心我们的整数类型的大小(以及它所暗示的范围)。因此，让我们从切换到cstdint*中定义的固定宽度整数类型开始。我们也应该改用未签名的品种。由于我们的代码只使用正整数，这实际上使溢出安全范围翻了一番：

uint32_t sum = 0;
uint32_t upLimit = 2000000;
uint32_t i = 2;
uint32_t j = i;

这是有帮助的，但最终还是会崩溃的。因此，让我们为我们想要存储在sum中的最大值建立一个上限。在这个领域里有一些非常有趣的数学，但是现在，让我们假装我们对素数一无所知。我们只知道我们会把不同的32位数相加。这是最多2^32的总和。最大可能值是2^32。这意味着sum不能超过2^32 * 2^32 = 2^64。我们有一种类型保证能够包含这样的内容：

uint64_t sum = 0;

别再溢出了。

如果您感兴趣，cstdint还包含类似于uint_fast32_t的类型定义，这样编译器就可以使用更大的类型，如果这样可以生成更高效的代码。例如，参见CppReference的cstdint。当然，通常关于过早优化的注意事项也适用。

最后一个技巧，与溢出无关：bool[]每个值占用1个字节，而std::vector<bool>则允许具有更高的空间效率。如果你想超过几百万的话，空间效率(以及更普遍的缓存友好性)将是最重要的。

*)这些定义需要C++11。如果这是不可用的，许多编译器在C++98模式下提供类似的类型，尽管可移植性可能会受到影响。或者，如果您的编译器支持C99，则可以从stdint.h获得固定宽度定义。

Answer 3

除了数据类型限制之外，尝试使用任何大于3的素数都可以表示为6x+1或6x-1的信息进行优化。

int sum = 5; // (2 + 3)
// For generic upLimit, i.e upLimit<4 have the conditional returns.
// Initialize the isPrime array with true.

// loop through i with i=5, check for i (6x-1), i+2 (6x+1) and then increase i by 6 
// (which is done in two steps i+=2 and i+=4.
for (int i=5; i<=upLimit; i+=4) {
    if (isPrime[i]) { // Prime 6x-1
        // add to sum
        sum += i;

        // mark all multiples
        int j = i;
        while (j <= upLimit) {
            isPrime[j] = false;
            j += i;
        }
    }
    i+=2;  // Prime 6x+1
    if (isPrime[i]) {
        // add to sum
        sum += i;

        // mark all multiples
        int j = i;
        while (j <= upLimit) {
            isPrime[j] = false;
            j += i;
        }
    }
}