-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: ああ、2 つのエラーが見つかりましたが、それらは問題を解決したようです。

1 つ目は、他の回答者が発見したもので、n がオーバーフローしているというものです。long long データ型にすると、機能し始めました。

2 番目の間違いは、r のブール値を初期化する必要があったことです。素数をチェックする前に loop を実行してすべての素数を false にすると、正しい答えが得られます。なぜこれが起こったのか誰か知っていますか？

4

1 に答える 1

2

整数オーバーフローが発生するだけです。C++ 型intの範囲は限られています (32 ビット システムでは、通常 -(2^32) / 2 から 2^32 / 2 - 1 です。つまり、通常の最大値は 2147483647 です (セットアップでの特定の最大値を見つけることができます)。k が最大値よりも小さい場合でも、コードは遅かれ早かれ式 or でオーバーフローを引き起こし<limits>ます。std::numeric_limits<int>::max()n += i + 2int j = 2 * i + 2

unsigned負の数をサポートしないため、 の 2 倍の大きさの数値を表すことができるような、より適切な (読み方: より適切な) 型を選択する必要がありますint。unsigned longまたはを試すこともできますunsigned long long。

また、可変長配列 (VLA; それが何でbool r[k - 2]あるか) は標準の C++ ではないことに注意してください。std::vector代わりに使用することもできます。また、配列を初期化していませんでしたfalse(std::vectorこれは自動的に行われます)。これは、特に k=500 でも機能しないと言う場合に問題になる可能性があります。

C++ では、<ctime>代わりに<time.h>(thenclock_tと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 に答える