判断素数的基础方法是试除法，从2到√n逐一试除，若存在整除则非素数；优化时只需检查2和奇数，进一步可用埃氏筛预处理提升多查询效率。
判断一个数是否为素数（质数）是C++编程中的常见问题。基础思路简单，但随着数值增大，算法效率差异明显。下面从基础实现出发，逐步优化，提升运行效率。
基础方法：试除法
最直接的方法是从2开始，尝试用小于n的所有数去除n，若存在能整除的数，则n不是素数。
bool isPrime(int n) {if (n if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i if (n % i == 0)
return false;
}
return true;
}
这种方法逻辑清晰，但当n较大时，循环次数太多，效率低下。
优化1：只检查到√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;
}
这里跳过偶数（除了2），只检查奇数，将循环次数减少近一半。i * i
优化2：预处理小素数 + 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;
}
该方法先排除能被2或3整除的数，然后从5开始，每次检查i和i+2（即6k-1和6k+1），步长为6。在大数判断中性能显著提升。
批量判断：埃拉托斯特尼筛法
如果需要判断多个数是否为素数，特别是范围连续的情况，使用筛法更高效。
#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)，空间换时间。
基本上就这些。单次判断用6k±1优化，多次判断优先考虑筛法。关键在于根据场景选择合适方法，避免无谓计算。
