C++素数筛法

简介：
C++素数筛法介绍的是利用C++编程语言实现寻找一定范围内所有素数的算法，主要包括埃拉托斯特尼筛法和欧拉筛法等高效筛选技术。 本段落介绍了筛选法在C++中的实现方式。筛选法是一种用于找出不超过自然数N（N>1）的所有质数的方法，又称为埃拉托斯特尼筛子，由古希腊数学家埃拉托斯特尼发明。 使用C++编程语言来执行埃拉托斯特尼筛子算法可以高效地在一定范围内找到所有素数。该方法通过一系列排除步骤确定并输出那些仅能被1和自身整除的自然数（即素数）。其核心思想是从最小的奇质数开始，将它的倍数标记为非素，并不断重复此过程直到遍历到范围内的平方根。 下面展示了一个C++实现的例子： ```cpp #include #include #define MAX 100 using namespace std; int main() { int prime[MAX + 1]; // 初始化数组，偶数标记为非素数（0），奇数可能为素数（1） for (int i = 1; i <= MAX; i++) { if (i % 2 == 0) { prime[i] = 0; } else { prime[i] = 1; } } // 找出所有的奇质数，并将其倍数标记为非素 for (int i = 3; i <= sqrt(MAX); i++) { if (prime[i] == 1) { for (int j = i + i; j <= MAX; j += i) { prime[j] = 0; } } } // 输出2，因为它是唯一的偶数素数 cout << 2 ; // 找出并输出剩余的奇质数 for (int i = 3; i <= MAX; i++) { if (prime[i] == 1) { cout << i << ; } } return 0; } ``` 这段代码首先创建了一个大小为MAX+1的数组`prime`，用于记录每个数是否是素数。初始时偶数被标记为非素（0），奇数可能为素（1）。接着从3开始遍历所有未排除的数字，并将它们的所有倍数设为非素。最后输出2和其它所有的奇质数。 该算法的时间复杂度大约为O(n log log n)，空间复杂度是O(n)。因此，它对于查找较大范围内的素数非常有效率。在实际应用中可以根据需要调整MAX的值以适应不同的需求。