-1

素数を見つける途中でいくつかの要素を削除できるセットになるため、配列だけを使用して有名なエラトステネスのふるいを C++ でコーディングしたいと思います。STL (ベクター、セット) は使いたくない... 配列だけ! どのように私はそれを実現することができますか？

STL 集合演算子を使用したくない理由を説明しようとしています: 私は C++ を最初から学んでおり、STL はもちろんプログラマーにとって便利だと思いますが、標準ライブラリ上に構築されているので、以前の演算子を使用したいと思います。とコマンド。STL を使えばすべてが簡単になることはわかっています。

4

2 に答える 2

2

エラトステネスの効率のふるい分けの鍵は、複合体を列挙する際に複合体を削除/削除/破棄/などせず、そのようにマークするだけであるということです。

すべての数値を保持することで、数値の値をこの配列のアドレスとして使用できるため、直接アドレス指定することができますarray[n]。これが、最新のランダム アクセス メモリコンピューターに実装された場合に、ふるいの列挙と各素数の倍数のマーク付けを効率的にするものです (整数ソート アルゴリズムと同様)。

その配列がセットをシミュレートするようにするために、各エントリに 2 つの可能な値、フラグ:onとoff、primeまたはcomposite、1またはを与えます0。はい、実際には、作業中にそれらのいずれも削除しない限り、 sieve 配列内の各数値を表すために、バイトではなく1ビットのみが必要です。

ところで、vector<bool>は自動的にパックされ、bools をビット単位で表します。とても便利。

于 2013-08-21T06:28:11.287 に答える
1

アルゴリズムとデータ構造から

#include<iostream>
#include<cmath>
#include<cstring>

using namespace std;

void runEratosthenesSieve(int upperBound) {

      int upperBoundSquareRoot = (int)sqrt((double)upperBound);
      bool *isComposite = new bool[upperBound + 1];
      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));

      for (int m = 2; m <= upperBoundSquareRoot; m++) {  
            if (!isComposite[m]) {
                  cout << m << " ";
                  for (int k = m * m; k <= upperBound; k += m)
                        isComposite[k] = true;
            }
      }
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)
            if (!isComposite[m])
                  cout << m << " ";

      delete [] isComposite;
}


int main()
{
 runEratosthenesSieve(1000);
}

STL を使用したくないが、それは良い考えではありません

STL は生活をよりシンプルにします。

を使用してこの実装を検討してくださいstd::map

int  max = 100;
S sieve;

for(int it=2;it < max;++it)
    sieve.insert(it);

for(S::iterator it = sieve.begin();it != sieve.end();++it)
{
    int  prime   = *it;
    S::iterator x = it;
    ++x;
    while(x != sieve.end())
        if (((*x) % prime) == 0)
            sieve.erase(x++);
        else
            ++x;
}

for(S::iterator it = sieve.begin();it != sieve.end();++it)
 std::cout<<*it<<std::endl;
于 2013-08-18T18:21:21.847 に答える