エラトステネスのふるいを実装しています。最初のステップ、つまり使用するデータ構造の決定に行き詰まっています。簡単に言えば、エラトステネスのふるいは連続した数字のリストから始まります (例: 2、3、4、5、...99、100)。次に、特定の数字が取り消し線で消され、二度と考慮されなくなります。使用するのに最適なデータ構造は何ですか? 制限 (例では 100) は実行時までわかりませんが、常に開始数は 2 です。
私はいくつかの異なる解決策を見てきました。制限nはタイプですmpz_class
bool primes[n]bool* primesstd::vector<bool> primesstd::bitset<n> primesvectorパラメータを使用するintかunsigned char、より効率的であるためbool- ベクトルおよび配列ベースのソリューションの場合、
n+1要素を割り当てます（ここで見られるnように）これは、の値が最後の要素になり、ループ内で必要な減算が少なくなるためだと思います。
この情報の一部は、このコード レビューの質問から得られます。@Jamal は、「実際には std::vector に特に問題がある」と述べていますが、詳しくは述べていません。また、より良い選択をするよりもunsigned char、サイズが等しいか小さいことが保証されている場所を赤くします。 bool