c++ 判断是不是质数

以下是一个 C++ 实现判断一个数是否为素数的函数： ```c++ bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } ``` 该函数使用了一个常见的算法，即从 2 开始枚举所有可能的因子，如果找到一个因子就可以判定该数不是素数，否则该数是素数。优化的关键在于，只需要枚举到 sqrt(n) 即可，因为如果 n 不是素数，那么它一定有一个小于 sqrt(n) 的因子和一个大于 sqrt(n) 的因子。

### C++ 实现判断质数的几种方法 #### 方法一：简单试除法 此方法通过遍历从 `2` 到 `√n` 的所有整数来检查是否存在能整除 `n` 的因子。这种方法适用于较小范围内的数值。 ```cpp #include <cmath> // 导入 sqrt 函数所需的头文件 bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); ++i) { // 只需测试至 √n 即可 if (n % i == 0) return false; } return true; } ``` 上述代码展示了如何利用简单的循环结构和取模运算符 `%` 来检测给定正整数是否为质数[^2]。 #### 方法二：埃拉托斯特尼筛法（Eratosthenes Sieve） 该算法用于一次性找出某个范围内所有的质数，效率较高，尤其适合处理大量连续自然数的情况。时间复杂度接近 O(n log log n)，空间复杂度取决于所选区间的大小。 ```cpp const int MAXN = 1e7 + 5; bool not_prime[MAXN]; void sieve() { memset(not_prime, 0, sizeof(not_prime)); not_prime[0] = not_prime[1] = true; for (long long i = 2; i * i < MAXN; ++i) if (!not_prime[i]) for (long long j = i * i; j < MAXN; j += i) not_prime[j] = true; } // 使用前先调用一次 sieve() if (!not_prime[n]) puts("Yes"); else puts("No"); ``` 这段程序实现了经典的埃氏筛选过程，并提供了一个便捷的方式去查询任意单个数字是否属于之前已经标记好的质数集合中的一员[^3]。 #### 方法三：线性筛法（Linear Sieve 或 Euler Sieve） 相比于传统的埃拉托斯特尼筛法，在某些情况下可以进一步优化性能，达到几乎线性的运行速度 O(n)。其核心思想在于避免重复标记合数以及减少不必要的乘法操作次数。 ```cpp vector<int> primes; bitset<MAXN> is_composite; void linear_sieve(int limit) { for (int i = 2; i <= limit; ++i) { if (!is_composite[i]) primes.push_back(i); for (size_t j = 0; j < primes.size() && i * primes[j] <= limit; ++j) { is_composite[i * primes[j]] = true; if (!(i % primes[j])) break; } } } // 查询某数是否为质数 auto it = lower_bound(primes.begin(), primes.end(), n); if (it != end(primes) && (*it) == n) puts("Yes"); else puts("No"); ``` 这里展示了一种更高效的线性筛法版本，它不仅能够快速找到指定区间内的全部质数列表，而且支持高效地验证特定值是不是质数成员之一。 每一种方法都有各自的适用场景和技术特点，选择哪种具体依赖于实际应用场景的需求分析结果。