C++如何判断质数

### C++ 中判断质数的实现方法 在 C++ 编程语言中，有多种方式可以用来判断一个整数是否为质数（也称为素数）。以下是几种常见的实现方法及其对应的算法。 #### 方法一：简单枚举法 这种方法通过遍历从 `1` 到 `n` 的所有可能除数来检查是否存在除了 `1` 和其本身以外的其他因子。如果存在，则该数不是质数；否则就是质数[^1]。 ```cpp #include <iostream> using namespace std; int main() { int i, n, count = 0; cin >> n; for (i = 1; i <= n; i++) { if (n % i == 0) // 筛选出因子只有1和它本身的数 count++; } if (count == 2) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; } ``` 此方法的时间复杂度较高，为 O(n)，因此仅适用于较小范围内的数值测试。 --- #### 方法二：优化后的标记法 为了提高效率，可以通过减少循环次数来进行改进。具体来说，在检测某个数是否能被更小的自然数整除时，只需考虑不超过平方根的部分即可。这是因为任何大于 sqrt(n) 的因数必然对应一个小于 sqrt(n) 的配对因数[^2]。 ```cpp #include <iostream> #include <cmath> // 使用 cmath 库中的 sqrt 函数 using namespace std; int main() { int n; cin >> n; bool flag = false; for (int i = 2; i <= sqrt(n); i++) { // 只需迭代至 √n 即可 if (n % i == 0) { flag = true; break; } } if (!flag && n != 1) { cout << "Yes"; } else { cout << "No"; } return 0; } ``` 这种做法显著降低了时间消耗，特别是对于较大的输入数据而言更为高效，其平均性能接近 O(√n)。 --- #### 方法三：埃拉托斯特尼筛法（Sieve of Eratosthenes） 当需要找出一定区间内所有的质数时，“埃氏筛”是一种非常有效的手段之一。基本原理是从第一个质数开始依次划掉它的倍数直到目标上限为止[^3]。 ```cpp #include <iostream> const int MAXN = 1e7 + 5; bool isPrime[MAXN]; void sieveOfEratosthenes(int limit){ memset(isPrime,true,sizeof(bool)*limit); isPrime[0]=isPrime[1]=false; for(long long p=2;p*p<=limit;p++){ if(isPrime[p]){ for(long long multiple=p*p;multiple<limit;multiple+=p){ isPrime[multiple]=false; } } } } int main(){ int num; cin>>num; sieveOfEratosthenes(num+1); if(isPrime[num])puts("Yes"); else puts("No"); return 0; } ``` 上述代码片段展示了如何利用布尔数组记录哪些索引位置代表的是质数状态，并最终依据查询值返回相应结果。相比前两种单独验证单个数字的方式，这里更适合批量处理多个候选者的情况。 --- #### 总结说明 以上介绍了三种不同层次上的解决思路——从最基础逐一尝试每个潜在因素到最后采用预计算策略快速定位答案。实际应用过程中可根据具体情况选择合适的技术方案加以实施。