判断一个数是否是质数（素数）是一个经典的算法问题。质数是指大于 1 的自然数，且只能被 1 和它本身整除的数。以下是几种常见的判断质数的算法及其优化。
1. 朴素算法
从 2 到 n-1 逐一检查是否能整除 n。如果能被整除，则 n 不是质数。
bool isPrime(int n) {if (n <= 1) return false; // 1 及以下的数不是质数for (int i = 2; i < n; i++) {if (n % i == 0) return false; // 如果能被整除，不是质数}return true; // 否则是质数
}
时间复杂度：O(n)
缺点：效率低，尤其对于大数。
2. 优化：只检查到 √n
如果一个数 n 不是质数，那么它一定有一个因数小于或等于 √n。因此，只需要检查到 √n 即可。
bool isPrime(int n) {if (n <= 1) return false;for (int i = 2; i * i <= n; i++) { // 只需检查到 √nif (n % i == 0) return false;}return true;
}
时间复杂度：O(√n)
优点：效率显著提高。
3. 进一步优化：跳过偶数
除了 2，所有偶数都不是质数。因此，可以跳过所有偶数。
bool isPrime(int n) {if (n <= 1) return false;if (n == 2) return true; // 2 是质数if (n % 2 == 0) return false; // 排除偶数for (int i = 3; i * i <= n; i += 2) { // 只检查奇数if (n % i == 0) return false;}return true;
}
时间复杂度：O(√n)，但实际运行时间减半。
4. 进一步优化：6k ± 1 规则
所有质数（除了 2 和 3）都可以表示为 6k ± 1 的形式。因此，可以只检查形如 6k ± 1 的数。
bool isPrime(int n) {if (n <= 1) return false;if (n <= 3) return true; // 2 和 3 是质数if (n % 2 == 0 || n % 3 == 0) return false; // 排除 2 和 3 的倍数for (int i = 5; i * i <= n; i += 6) { // 只检查 6k ± 1 的数if (n % i == 0 || n % (i + 2) == 0) return false;}return true;
}
时间复杂度：O(√n)，但实际运行时间更少。
5. 素数筛法（适合批量判断）
如果需要判断多个数是否是质数，可以使用 埃拉托斯特尼筛法（Sieve of Eratosthenes）预处理。
#include <vector>
#include <cmath>vector<bool> sieve(int n) {vector<bool> isPrime(n + 1, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i * i <= n; i++) {if (isPrime[i]) {for (int j = i * i; j <= n; j += i) {isPrime[j] = false;}}}return isPrime;
}bool isPrime(int n) {if (n <= 1) return false;vector<bool> primes = sieve(n);return primes[n];
}
时间复杂度：O(n log log n)（预处理），O(1)（查询）。
优点：适合批量判断。
6. Miller-Rabin 素性测试（适合大数）
对于非常大的数（如 100 位以上的数），可以使用 Miller-Rabin 素性测试。这是一种概率算法，但可以通过多次测试将错误率降到极低。
#include <cstdlib>
#include <ctime>using ll = long long;ll power(ll a, ll d, ll n) {ll result = 1;a = a % n;while (d > 0) {if (d % 2 == 1) result = (result * a) % n;d = d >> 1;a = (a * a) % n;}return result;
}bool millerTest(ll d, ll n) {ll a = 2 + rand() % (n - 4);ll x = power(a, d, n);if (x == 1 || x == n - 1) return true;while (d != n - 1) {x = (x * x) % n;d *= 2;if (x == 1) return false;if (x == n - 1) return true;}return false;
}bool isPrime(ll n, int k = 5) {if (n <= 1 || n == 4) return false;if (n <= 3) return true;ll d = n - 1;while (d % 2 == 0) d /= 2;for (int i = 0; i < k; i++) {if (!millerTest(d, n)) return false;}return true;
}
时间复杂度：O(k log³ n)，其中 k 是测试次数。
优点：适合大数判断。
总结
- 对于小范围数（如
n ≤ 10^6），使用 优化到 √n 或 6k ± 1 规则 的算法即可。 - 对于大范围数（如
n ≤ 10^12），可以使用 Miller-Rabin 素性测试。 - 如果需要批量判断，使用 埃拉托斯特尼筛法。