C++ 中的 Eratosthenes 篩子演算法
本文將講解如何在 C++ 中實現 eratosthenes 的篩子演算法。
在 C++ 中使用 std::vector 容器實現 Eratosthenes 篩子演算法
Eratosthenes 篩法是素數篩法之一，代表了尋找素數的相對高效的演算法。有多種演算法適用於不同的素數範圍，並且它們也具有對比的效能特徵。
Eratosthenes 篩法可以被認為是最容易實現的，它在較小的範圍內非常有效。儘管它的執行時間複雜度是 O(N loglogN)，但它在較小的範圍內表現更好。
本文將使用適合介紹性文章的最直接的方法來實現該演算法。該演算法採用整數值並找到所有小於或等於給定整數的素數。
首先，我們構造一個布林值陣列，其大小與給定的整數相同，並將每個元素初始化為具有 true 值。
然後我們遍歷這個元素陣列並儲存 false 值，如果給定元素具有複合索引。我們通過從最小的一個 - 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
前面的程式碼片段是一個工作示例，可以使用各種方法進行優化，例如利用程式中的併發性、切片並將陣列儲存在記憶體中以便優化資料訪問，或使用其他演算法見解。儘管如此，有一個微小的見解可以在不進行大量更改的情況下為該實現節省數倍的執行時間，那就是將 true/false 值儲存在 char 向量中。
正如你通過對較大數字執行多個測試所觀察到的那樣，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
