-2

我已经用 C++ 编写了一个 Eratosthenes 算法的筛子，它适用于我测试过的较小的数字。但是，当我使用大数字，即 2 000 000 作为上限时，程序开始给出错误的答案。谁能澄清为什么？

感谢您的帮助。

#include <iostream>
#include <time.h>
using namespace std;

int main() {
    clock_t a, b;
    a = clock();

    int n = 0, k = 2000000; // n = Sum of primes, k = Upper limit
    bool r[k - 2]; // r = All numbers below k and above 1 (if true, it has been marked as a non-prime)
    for(int i = 0; i < k - 2; i++) // Check all numbers
        if(!r[i]) { // If it hasn't been marked as a non-prime yet ...
            n += i + 2; // Add the prime to the total sum (+2 because of the shift - index 0 is 2, index 1 is 3, etc.)
            for(int j = 2 * i + 2; j < k - 2; j += i + 2) // Go through all multiples of the prime under the limit
                r[j] = true; // Mark the multiple as a non-prime
        }

    b = clock();
    cout << "Final Result: " << n << endl;
    cout << b - a << "ms runtime achieved." << endl;
    return 0;
}

编辑：我刚刚进行了一些调试，发现它可以在 400 左右的限制下工作。但是，在 500 时，它关闭了 - 它应该是 21536，但是是 21499

编辑2：啊，我发现了两个错误，这些似乎已经解决了问题。

第一个是由其他回答的人发现的，并且 n 溢出 - 在被设为 long long 数据类型后，它已经开始工作。

第二个相当值得大惊小怪的错误是 r 中的布尔值必须被初始化。在检查素数以使它们全部为假之前运行循环之后，得到正确的答案。有谁知道为什么会这样？

4

1 回答 1

2

你只是得到一个整数溢出。C++ 类型int的范围有限（在 32 位系统上，通常从 -(2^32) / 2 到 2^32 / 2 - 1，即通常的最大值为 2147483647（可以找到您设置的具体最大值通过 #include<limits>标头和评估std::numeric_limits<int>::max(). 即使 k 小于最大值，您的代码迟早会导致表达式n += i + 2或int j = 2 * i + 2.

您将不得不选择一种更好（阅读：更合适）的类型，例如unsigned它不支持负数，因此可以表示两倍于int. 你也可以试试unsigned long，甚至unsigned long long。

另请注意，可变长度数组（VLA；就是这样bool r[k - 2]）不是标准 C++。您可能想std::vector改用。您也没有将数组初始化为false（std::vector会自动执行此操作），这也可能是问题所在，特别是如果您说即使在 k=500 时它也不起作用。

在 C++ 中，您还应该使用<ctime>( <time.h>then clock_tand andclock() are defined in thestd namespace, but since you areusing namespace std` 来代替，这不会对您产生影响），但这或多或少是一个风格问题。

我在我的“代码档案”中找到了一个工作示例。虽然它不是基于您的，但您可能会发现它很有用：

#include <vector>
#include <iostream>

int main()
{
    typedef std::vector<bool> marked_t;
    typedef marked_t::size_type number_t; // The type used for indexing marked_t.

    const number_t max = 500;

    static const number_t iDif = 2; // Account for the numbers 1 and 2.
    marked_t marked(max - iDif);
    number_t i = iDif;

    while (i*i <= max) {
        while (marked[i - iDif] == true)
            ++i;
        for (number_t fac = iDif; i * fac < max; ++fac)
            marked[i * fac - iDif] = true;
        ++i;
    }

    for (marked_t::size_type i = 0; i < marked.size(); ++i) {
        if (!marked[i])
            std::cout << i + iDif << ',';
    }
}
于 2013-03-03T19:20:56.640 回答