2

これは、効率の悪い素数ジェネレーターと見なされますか。これはかなり効率的だと私には思えます。プログラムの実行を遅くするのはストリームの使用ですか?

これをSPOJに提出しようとしていますが、制限時間を超えていると表示されます...

#include <iostream>
#include <sstream>

using namespace std;

int main() {
    int testCases, first, second, counter = 0;
    bool isPrime = true;
    stringstream out;

    cin >> testCases;

    for (int i = 0; i < testCases; i++) {
        // get the next two numbers
        cin >> first >> second;

        if (first%2 == 0)
            first++;

        // find the prime numbers between the two given numbers
        for (int j = first; j <= second; j+=2) {
            // go through and check if j is prime
            for (int k = 2; k < j; k++) {
                if (j%k == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                out << j << "\n";
            }
            isPrime = true;
        }
        out << "\n";
    }

    cout << out.str();

    return 0;
}

編集: プログラムは、入力で指定された数値の間に素数を生成することになっています。(詳細については、ここを参照してください:プライム ジェネレーターの問題)

-トメク

4

6 に答える 6

14

これは単純なアルゴリズムよりも 1 ステップ上 (偶数をスキップ) です。より効率的なアルゴリズムとして、エラトステネスのふるいをお勧めします。上記のリンクから：

アルゴリズムの複雑さは O((nlogn)(loglogn)) で、メモリ要件は O(n) です。ホイール因数分解などの基本的な最適化を備えたエラトステネスのふるいのセグメント化されたバージョンは、O(n) 操作と O(n1 / 2loglogn / logn) ビットのメモリを使用します。

あなたが与えるアルゴリズムは、O（n ^ 2）の近くにあります。偶数をスキップすることで得られる高速化は、最初のテストで偶数が素数ではないことがわかるため、それほど大きくはありません。Sieve のメモリ要件ははるかに大きくなりますが、実行時の複雑さはNが大きいほどはるかに優れています。

于 2008-10-23T20:36:08.450 に答える
7

必要以上に多くの番号を検索しています。せいぜい に行くだけです<= (sqrt(num))。

于 2008-10-23T20:36:48.433 に答える
4

これは、エラトステネスの単純なふるいです。大きなブール配列を事前に宣言する必要はありませんが、それでも時間と空間は >>O(n) です。ただし、十分なメモリがある限り、現在の素朴な方法よりも著しく高速になるはずです。

#include <iostream>
#include <map>

using namespace std;

template<typename T = int, typename M = map<T, T> >
class prime_iterator {
    public:
        prime_iterator() : current(2), skips() { skips[4] = 2; }
        T operator*() { return current; }
        prime_iterator &operator++() {
            typename M::iterator i;
            while ((i = skips.find(++current)) != skips.end()) {
                T skip = i->second, next = current + skip;
                skips.erase(i);
                for (typename M::iterator j = skips.find(next);
                        j != skips.end(); j = skips.find(next += skip)) {}
                skips[next] = skip;
            }
            skips[current * current] = current;
            return *this;
        }
    private:
        T current;
        M skips;
};

int main() {
    prime_iterator<int> primes;
    for (; *primes < 1000; ++primes)
        cout << *primes << endl;
    return 0;
}

それでも遅い場合は、最適化されたエラトステネスのふるいであるアトキンのふるいを追求することをお勧めします。

実際には、これらは、生成する素数の範囲が低く始まる場合にのみ比較的効率的です。下限がすでにかなり大きく、上限が下限よりもそれほど大きくない場合、ふるい分け方法は無駄な作業であり、素数性テストを実行する方がよいでしょう。

于 2008-10-24T22:45:16.523 に答える
3

そしてもう1つ、ループでsqrt（n）を使用しないでください。

for(int k=1;k<sqrt(n);++k)

適切な最適化がない場合、sqrtはすべての反復で計算されます。

使用する

for (int k=1;k*k < n;++k)

または単に

int sq = sqrt ( n );
for (int k=1;k<sq;++k)
于 2009-07-04T08:34:58.047 に答える
0

もう少し効率化できます。k を 2 から始める必要はありません。すでに偶数をテストしないようにしています。したがって、k は 3 から開始し
ます。他の偶数をテストする必要がないため、毎回 k を 2 ずつ増やします。私が考えることができる最も効率的な方法は、数値が既知の素数で割り切れるかどうかのみをテストすることです (別の素数が見つかったら、テストするリストにそれを追加します)。

于 2008-10-23T20:38:19.960 に答える
0 
for (int k = 2; k < j; k++) {
     if (j%k == 0) {
         isPrime = false;
         break;
     }
}

次のようにする必要があります。

for(int k = 3; k <= j/2; k+=2 )
{
  if( j % k == 0 )
      break;
}

j/2 は実際には sqrt(j) である必要がありますが、通常は十分な推定値です。

于 2008-10-23T20:40:43.027 に答える