この素数ジェネレーターは非効率なC ++ですか？

StackOverflow https://stackoverflow.com/questions/231381

  •  04-07-2019
  •  | 
  •  

質問

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

これを 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;
}

EDIT：プログラムは、入力で指定された数の間の素数を生成することになっています。 （詳細については、 Prime Generatorの問題を参照してください）

-Tomek

役に立ちましたか？

解決

これは、単純なアルゴリズムの1ステップ（偶数をスキップ）です。より効率的なアルゴリズムとして、 Sieve Of Eratosthenes をお勧めします。上記のリンクから：

  

アルゴリズムの複雑さは   O（（nlogn）（loglogn））メモリ付き   O（n）の要件。セグメント化   エラトステネスのふるいのバージョン、   ホイールなどの基本的な最適化   分解、O（n）操作を使用   およびO（n1 / 2 loglogn / logn）ビット   メモリ。

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

他のヒント

必要以上に多くの数字を検索している-せいぜい<= (sqrt(num))に行くだけでよい。

これは簡単なエラトステネスのふるいです。大きなブール配列を事前宣言する必要はありませんが、時間と空間では<！> gt; <！> gt; O（n）のままです。ただし、十分なメモリがある限り、現在のna <！>＃239; veメソッドよりも著しく高速である必要があります。

#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;
}

これでもまだ遅すぎる場合は、アトキンのふるい、エラトステネスの最適化されたふるい。

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

もう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)

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

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）である必要がありますが、通常は十分な推定値です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top