判断素数的高效方法是检查2到√n间的因子。基础优化：n<2非素数，遍历2至√n，整除则非素数，否则为素数。
判断一个数是否为素数（质数）是C++编程中的常见问题。素数是指大于1且只能被1和自身整除的自然数。最简单的实现方式是从2遍历到n-1，但效率极低。下面介绍几种高效且实用的C++实现方法。
基础优化：只检查到√n
一个合数必然有一个小于或等于其平方根的因子。因此，我们只需检查从2到√n之间的所有数即可。
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 * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
这个版本跳过了所有偶数（除了2），减少了约一半的循环次数，适用于中等大小的数（如n < 1e9）。
进一步优化：6k±1 法则
除了2和3，所有素数都可以表示为6k±1的形式。利用这一点可以大幅减少判断次数。
立即学习“C++免费学习笔记（深入）”；
bool isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
该方法先排除能被2或3整除的数，然后从5开始，每次检查i和i+2（即6k-1和6k+1），步长为6。在实际测试中比前一种更快。
处理大数：Miller-Rabin 概率算法
当n非常大（如超过1e18）时，确定性算法太慢。Miller-Rabin是一种高效的概率性素数测试算法，适合大数场景。
基本思路是基于费马小定理和二次探测定理，通过多次随机测试来判断是否“极大概率”为素数。
#include <bits/stdc++.h>
using namespace std;
<p>long long modMul(long long a, long long b, long long mod) {
return (__int128)a * b % mod;
}</p><p>long long modPow(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp & 1) result = modMul(result, base, mod);
base = modMul(base, base, mod);
exp >>= 1;
}
return result;
}</p><p>bool millerRabin(long long n, long long a) {
if (n % a == 0) return false;
long long d = n - 1;
while (d % 2 == 0) {
if (modPow(a, d, n) == n - 1) return true;
d >>= 1;
}
long long temp = modPow(a, d, n);
return temp == 1 || temp == n - 1;
}</p><p>bool isPrime(long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;</p><pre class='brush:php;toolbar:false;'>// 对于 32 位整数，使用这些底数可保证正确性
vector<long long> bases = {2, 7, 61};
for (long long a : bases) {
if (a >= n - 1) break;
if (!millerRabin(n, a)) return false;
}
return true;}
该实现对32位以内的整数完全准确。对于更大的数，可增加测试底数（如2, 325, 9375, 28178, 450775, 9780504, 1795265022）以提高准确性。
基本上就这些。小数用6k±1法足够快，大数考虑Miller-Rabin。关键在于根据数据范围选择合适的方法。
