本文共 1842 字，大约阅读时间需要 6 分钟。
最近在学习C++编程，我决定尝试实现一个质数筛选算法——埃式筛法。埃式筛法是一种高效的筛选质数的方法，以前在数学课上老师也简单提到过，但一直没机会深入实践。下面我将一步一步记录我的实现过程。
首先，我需要准备一些必要的头文件。质数判断和筛选常用到的标准库包括<iostream>和<string>, 所以我在代码最开始处包含了这两个头文件：
#include#include
接着，我还需要使用<cstdio>来处理标准输入输出，以及<cstring>来操作字符串函数：
#include#include
为了方便使用，我在代码的最顶部声明了using namespace std;，这样可以在代码中直接使用std::中的函数和类别，而无需每次都写std::：
using namespace std;
接下来，我定义了几个辅助变量和函数。首先是isprime数组，用来记录哪些数是质数。由于常见的质数范围较大，我定义了一个长度为10000001的数组isprime，并初始化isprime[1]为true，因为1通常不被认为是质数：
bool isprime[10000001];isprime[1] = true;
然后是p数组，用于记录每个数的质数前置数。p[i]表示i的最小质因数：
int p[10000001];p[1] = 0;
接下来是void sieve(int n)函数，用于实现埃式筛法：
void sieve(int n){ if(n < 2) return; p[1] = 0; isprime[1] = true; for(int i = 2; i <= n; i++) { if(isprime[i] == false) { p[i] = p[i - 1] + 1; for(int j = i * i; j <= n; j += i) { isprime[j] = true; } } else p[i] = p[i - 1]; }} 最后是int main()主函数，用于实现对质数的判断：
int main(){ int a, b; scanf("%d%d", &a, &b); sieve(a); for(int i = 1; i <= b; i++) { int x; scanf("%d", &x); if(!isprime[x]) printf("Yes\n"); else printf("No\n"); } return 0;} 整个程序的实现过程如上所述。通过调用void sieve(int n)函数，我们可以生成一个质数数组isprime，其中isprime[i]为true表示i是质数。然后，我们可以通过isprime数组快速判断输入的数字是否为质数。
在编写代码的过程中，我也遇到了一些需要注意的地方：
初始值设置：isprime[1]被初始化为true，但在质数判断中，1通常不被认为是质数。因此，在isprime[x]判断时，需要特别注意这一点。
循环条件：在筛选过程中，外层循环的终止条件是i <= n。内层循环的条件是j = i * i; j <= n; j += i，这样可以避免重复筛选多次。
性能优化：埃式筛法的时间复杂度是O(n log log n)，对于较大的数值来说，性能非常优异。在实际应用中，可以根据需要调整筛选范围。
输入处理：在主函数中，使用scanf函数读取输入数据。需要注意的是，scanf函数会自动处理输入的空格和换行符，因此在读取多个数字时，可以直接连续使用scanf函数。
通过上述实现，我成功地将埃式筛法在C++语言中实现出来，并能够根据输入的两个数值快速判断另一个数值是否为质数。这对于解决实际问题具有重要的意义。
转载地址：http://ucvfk.baihongyu.com/