答案是判断素数常用试除法，从2到√n依次试除，若存在整除则非素数，优化方法包括只检查奇数和使用埃氏筛法预处理。
判断一个数是否为素数是C++编程中的常见问题。素数是指大于1且只能被1和自身整除的自然数，比如2、3、5、7、11等。下面介绍几种常用的C++判断素数的方法，从基础到优化逐步讲解。
1. 基础方法：试除法
最直接的方法是尝试用2到n-1之间的所有数去除n，如果存在能整除的数，则n不是素数。
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i < n; i++) {
if (n % i == 0)
return false;
}
return true;
}
说明： 这种方法简单直观，但效率低，时间复杂度为O(n)，不适合大数判断。
2. 优化方法：只检查到√n
如果n有一个大于√n的因数，那么必然有一个小于√n的对应因数。因此只需检查从2到√n即可。
立即学习“C++免费学习笔记（深入）”；
#include <cmath>
<p>bool isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0)
return false;
}
return true;
}</p>说明： 排除了偶数后只检查奇数，将循环次数减少一半，时间复杂度降到O(√n)，适用于大多数场景。
3. 进一步优化：预处理小素数 + 6k±1规律
除了2和3以外，所有素数都可以表示为6k±1的形式。可以利用这一点跳过更多合数。
bool isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
<pre class='brush:php;toolbar:false;'>for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;}
说明： 利用了素数分布规律，进一步减少循环次数，效率更高，适合频繁判断大数的情况。
4. 多次查询时使用埃氏筛法预处理
如果需要判断多个数是否为素数，可以预先用埃拉托斯特尼筛法（Eratosthenes Sieve）生成素数表。
#include <vector>
void sieveOfEratosthenes(int maxN, vector<bool>& prime) {
prime.assign(maxN + 1, true);
prime[0] = prime[1] = false;
for (int i = 2; i * i <= maxN; i++) {
if (prime[i]) {
for (int j = i * i; j <= maxN; j += i)
prime[j] = false;
}
}
}
<p>// 使用示例
vector<bool> prime;
sieveOfEratosthenes(100000, prime);
if (prime[97]) cout << "97是素数";</p>说明： 适合在已知范围内的多次查询，预处理O(n log log n)，单次查询O(1)。
基本上就这些常见的C++判断素数方法。根据实际需求选择：单次判断用优化试除法，大量查询用筛法。注意处理边界情况如n≤1、n=2等。不复杂但容易忽略细节。
