この素数ジェネレーターは非効率なC ++ですか?
-
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)である必要がありますが、通常は十分な推定値です。