C++ でのエラトステネスアルゴリズムのふるい
この記事では、エラトステネスのふるいアルゴリズムを C++ で実装する方法について説明します。
C++ で std::vector コンテナを使用してエラトステネスのふるいアルゴリズムを実装する
エラトステネスのふるいは素数のふるいの 1つであり、素数を求めるための比較的効率的なアルゴリズムを表しています。さまざまな素数範囲に適した複数のアルゴリズムがあり、それらには対照的なパフォーマンス特性もあります。
エラトステネスのふるいは、実装するのが最も簡単なものと見なすことができ、狭い範囲で非常に効率的です。実行時間の複雑さは O(N loglogN) ですが、範囲が狭いほどパフォーマンスが向上します。
この記事では、紹介記事に適した最も簡単な方法を使用して、このアルゴリズムを実装します。アルゴリズムは整数値を取り、指定された整数以下のすべての素数を見つけます。
最初に、指定された整数と同じサイズのブール値の配列を作成し、すべての要素を初期化して true 値にします。
次に、この要素の配列を反復処理し、指定された要素に複合インデックスがある場合は false 値を格納します。最小の素数（2）から開始して連続する素数の倍数を計算することにより、配列インデックスにアクセスし、指定された素数の 2 乗が入力整数（n）より大きくなると反復を停止します。前の手順は、printPrimesLessThanN 関数のネストされた for ループを使用して実装されています。
最後に、このベクトルを循環して、true 値が格納されている要素インデックスを出力します。後者の操作は、printPrimesLessThanN 関数の最後にある for ループによって処理されることに注意してください。また、main 関数にドライバーコードを提供して、ユーザーからの上限を示す整数を受け入れ、printPrimesLessThanN 関数に渡されるまで入力を検証します。
#include <cstring>
#include <iostream>
#include <limits>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
void printPrimesLessThanN(unsigned long long n) {
vector<bool> table(n, true);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == true) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = false;
}
}
for (unsigned long long p = 2; p < n; p++)
if (table[p]) cout << p << " ";
}
int main() {
unsigned long long integer;
while (true) {
cout << "Enter integer: ";
if (cin >> integer) {
break;
} else {
cout << "Enter a valid integer value!\n";
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
cout << "Following prime numbers are smaller than given integer: \n";
printPrimesLessThanN(integer);
return EXIT_SUCCESS;
}
出力：
Enter integer: 30
Following prime numbers are smaller than given integer:
2 3 5 7 11 13 17 19 23 29
前のコードスニペットは、プログラムでの同時実行性の活用、データアクセスが最適化されるように配列をスライスしてメモリに格納する、または他のアルゴリズムの洞察を使用するなど、さまざまな方法で最適化できる実用的な例です。ただし、大きな変更を加えることなく、この実装の実行時間を何倍も節約できる小さな洞察が 1つあります。それは、char のベクトルに true/false 値を格納することです。
より大きな数で複数のテストを実行することで観察できるように、bool タイプは、char や int のような整数タイプよりもパフォーマンスがかなり劣ります。次のコードサンプルは、関数の両方のバージョン（printPrimesLessThanN）の単純なベンチマークシナリオを示しており、プログラムの終了時に経過時間を出力します。
#include <sys/time.h>
#include <cstring>
#include <iostream>
#include <limits>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
float time_diff(struct timeval *start, struct timeval *end) {
return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}
void printPrimesLessThanN(unsigned long long n) {
vector<bool> table(n, true);
struct timeval start {};
struct timeval end {};
gettimeofday(&start, nullptr);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == true) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = false;
}
}
gettimeofday(&end, nullptr);
printf("printPrimesLessThanN1: %0.8f sec\n", time_diff(&start, &end));
}
void printPrimesLessThanN2(unsigned long long n) {
vector<char> table(n, 1);
struct timeval start {};
struct timeval end {};
gettimeofday(&start, nullptr);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == 1) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = 0;
}
}
gettimeofday(&end, nullptr);
printf("printPrimesLessThanN2: %0.8f sec\n", time_diff(&start, &end));
}
int main() {
unsigned long long integer;
while (true) {
cout << "Enter integer: ";
if (cin >> integer) {
break;
} else {
cout << "Enter a valid integer value!\n";
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
printPrimesLessThanN(integer);
printPrimesLessThanN2(integer);
return EXIT_SUCCESS;
}
出力：
Enter integer: 1000000000
printPrimesLessThanN1: 47.39665985 sec
printPrimesLessThanN2: 10.11181545 sec
