基础试除法：判断2到n-1是否能整除n；2. 优化试除法：只需检查2到√n；3. 跳过偶数：大于2的偶数非素数；4. 埃拉托斯特尼筛法：批量求素数高效。
判断一个数是否为素数（质数）是C++编程中常见的问题。素数是指大于1且只能被1和自身整除的自然数。下面介绍几种常用的算法，从简单到高效，适用于不同场景。
1. 基础试除法
最直观的方法是尝试用2到n-1之间的所有数去除n，如果存在能整除的数，则n不是素数。
bool isPrime(int n) {if (n if (n == 2) return true;
for (int i = 2; i if (n % i == 0)
return false;
}
return true;
}
这种方法逻辑清晰，但效率低，时间复杂度为O(n)，不适合大数判断。
2. 优化试除法：只检查到√n
如果n有一个大于√n的因数，那么必然有一个小于√n的对应因数。因此只需检查2到√n即可。
立即学习“C++免费学习笔记（深入）”；
bool isPrime(int n) {if (n if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i if (n % i == 0)
return false;
}
return true;
}
跳过偶数并只检查到√n，时间复杂度降为O(√n)，适合大多数实际应用。
3. 使用6k±1优化
除了2和3，所有素数都可以表示为6k±1的形式。可以利用这一点减少循环次数。
bool isPrime(int n) {if (n if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
该方法进一步减少了需要检查的数，性能比前一种更好，尤其在处理大数时优势明显。
4. 筛法预处理：埃拉托斯特尼筛法
如果需要判断多个数是否为素数，可以预先生成素数表。使用埃氏筛一次性标记出范围内的所有合数。
#include <vector>std::vector<bool> sieve(int n) {
std::vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i if (isPrime[i]) {
for (int j = i * i; j isPrime[j] = false;
}
}
return isPrime;
}
适用于需要频繁查询素数的场景，预处理时间复杂度为O(n log log n)，查询为O(1)。
基本上就这些常用方法。小数据用优化试除法，大数据或多次查询考虑筛法。理解每种算法的适用场景，能写出更高效的代码。
