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
