判断素数的基本概念
在数学中，素数（又称质数）是指大于1的自然数，除了1和它本身外，不能被其他自然数整除的数，2、3、5、7、11等都是素数，判断一个数是否为素数是编程中常见的数学问题，尤其在算法设计和数学计算领域应用广泛，在Java中实现素数判断，需要结合数学原理和编程逻辑,通过高效的算法来提升性能。
最基础的素数判断方法
试除法原理
最直观的素数判断方法是试除法，即从2开始，依次检查该数是否能被2到其平方根之间的整数整除，如果能被整除，则该数不是素数；否则，它是素数，这里使用平方根作为上限，是因为如果一个数n能被某个大于其平方根的数整除，那么它必然能被对应的小于平方根的数整除，因此无需检查大于平方根的数。
Java代码实现
以下是试除法的Java实现：
public static boolean isPrimeBasic(int num) {
if (num <= 1) {
return false; // 小于等于1的数不是素数
}
for (int i = 2; i * i <= num; i++) { // 从2到平方根
if (num % i == 0) {
return false; // 能被整除，不是素数
}
}
return true; // 是素数
}
代码分析
- 边界条件处理：首先排除小于等于1的数，因为素数定义中要求大于1。
- 循环优化：循环条件使用
i * i <= num而非i <= Math.sqrt(num)，避免了重复计算平方根，提升效率。 - 提前终止：一旦发现能被整除，立即返回
false，减少不必要的循环。
局限性
试除法虽然简单易懂，但在处理大数时效率较低，判断一个10位数的素数，可能需要循环数万次,因此仅适用于小规模数据或对性能要求不高的场景。
优化的素数判断方法
6k±1优化
数学上可以证明，所有大于3的素数都可以表示为6k±1的形式（k为正整数），在判断时可以跳过部分非素数情况，减少循环次数，具体优化思路：
- 先排除能被2或3整除的数。
- 从5开始，每次检查
i和i+2（即6k-1和6k+1），直到i * i > num。
Java代码实现
public static boolean isPrimeOptimized(int num) {
if (num <= 3) {
return num > 1; // 2和3是素数，1不是
}
if (num % 2 == 0 || num % 3 == 0) {
return false; // 排除能被2或3整除的数
}
for (int i = 5; i * i <= num; i += 6) { // 检查6k±1
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
优化效果
相比基础试除法，6k±1优化将循环次数减少了约2/3，判断num=10007时，基础方法需要循环约100次，而优化后仅需约17次,效率显著提升。
大数素数判断的特殊方法
当需要判断的数非常大时（如超过Integer.MAX_VALUE），上述方法的效率仍然不足，此时可以采用概率性算法（如Miller-Rabin测试）或确定性算法（如AKS算法）。
Miller-Rabin测试
Miller-Rabin是一种概率性素数测试算法，通过多次随机测试判断一个数是否为素数，虽然结果可能存在极小的错误概率，但通过增加测试次数，可以将错误概率降低到任意低。
Java代码实现（简化版）
import java.util.Random;
public static boolean isPrimeMillerRabin(long num, int iterations) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0) return false;
// 将num-1分解为d*2^s
long d = num - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
Random rand = new Random();
for (int i = 0; i < iterations; i++) {
long a = 2 + rand.nextLong(num - 4); // 随机选取a ∈ [2, num-2]
long x = modPow(a, d, num);
if (x == 1 || x == num - 1) continue;
for (int j = 0; j < s - 1; j++) {
x = modPow(x, 2, num);
if (x == num - 1) break;
}
if (x != num - 1) return false;
}
return true;
}
// 快速幂取模算法 (a^b % mod)
private static long modPow(long a, long b, long mod) {
long result = 1;
a = a % mod;
while (b > 0) {
if (b % 2 == 1) {
result = (result * a) % mod;
}
a = (a * a) % mod;
b /= 2;
}
return result;
}
代码说明
- 参数：
num为待判断的数，iterations为测试次数，次数越多结果越可靠（通常取5-10次）。 - 核心步骤：
- 分解
num-1为d*2^s，确保d为奇数。 - 随机选取基
a，计算a^d % num，若结果为1或num-1，则通过本次测试。 - 否则，重复平方
s-1次，若某次结果为num-1则通过；否则判定为合数。
- 分解
AKS算法
AKS算法是第一个多项式时间的确定性素数测试算法，理论意义大于实际应用，因为其常数因子较大，实际效率不如Miller-Rabin，此处不再展开,感兴趣可查阅相关资料。
特殊场景的素数判断
判断区间内的素数
若需要找出某个区间内的所有素数（如1到10000），可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes），该算法通过标记非素数的方式高效筛选素数。
Java代码实现
public static List<Integer> sieveOfEratosthenes(int maxNum) {
boolean[] isPrime = new boolean[maxNum + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= maxNum; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= maxNum; j += i) {
isPrime[j] = false;
}
}
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= maxNum; i++) {
if (isPrime[i]) {
primes.add(i);
}
}
return primes;
}
算法分析
- 时间复杂度：O(n log log n)，适合大规模区间素数筛选。
- 空间复杂度：O(n)，需要布尔数组记录每个数的素数状态。
判断超大数（BigInteger）
当数超过long范围时，可以使用java.math.BigInteger类，其内置了isProbablePrime()方法，基于Miller-Rabin测试实现。
Java代码示例
import java.math.BigInteger;
public static boolean isLargePrime(String numStr) {
BigInteger num = new BigInteger(numStr);
return num.isProbablePrime(10); // 参数为确定性测试次数
}
总结与建议
| 方法 | 适用场景 | 时间复杂度 | 特点 |
|---|---|---|---|
| 基础试除法 | 小数字，简单场景 | O(√n) | 代码简单，效率低 |
| 6k±1优化 | 中等数字 | O(√n)（常数更小） | 效率提升，代码稍复杂 |
| Miller-Rabin测试 | 大数字，高要求场景 | O(k log³n) | 概率性算法，可调可靠性 |
| 埃拉托斯特尼筛法 | 区间内所有素数 | O(n log log n) | 适合批量筛选 |
| BigInteger.isProbablePrime | 超大整数 | 依赖内部实现 | Java内置，方便可靠 |
在实际开发中，应根据数据规模和性能需求选择合适的方法，对于普通应用，6k±1优化已足够；对于密码学等高要求场景，建议使用Miller-Rabin或BigInteger内置方法，注意边界条件处理（如负数、0、1等）,确保代码的健壮性。
