在Java编程中，求素数是一个经典且基础的问题，素数是指大于1的自然数，除了1和它本身外不能被其他自然数整除的数，掌握素数的求解方法不仅有助于理解算法设计，还能提升代码优化能力，本文将详细介绍几种常见的Java素数求解方法,并分析其优缺点及适用场景。
基础判断法：试除法
最直观的素数判断方法是试除法，即从2开始到该数的平方根，依次检查是否存在能整除该数的数，若不存在，则该数为素数,以下是基础实现代码：
public static boolean isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
优化点：
- 排除小于等于1的数；
- 只需检查到平方根，因为若存在大于平方根的因数，必然对应一个小于平方根的因数；
- 步进可优化为2，跳过偶数（除2外）,进一步减少循环次数。
适用场景：适用于单个数的判断，但当需要求解一定范围内的所有素数时,效率较低。
埃拉托斯特尼筛法（筛法）
若需求解某一范围内的所有素数，筛法是更高效的选择，其核心思想是通过标记合数来筛选出素数，步骤如下：
- 初始化一个布尔数组
isPrime[]，标记所有数为素数（true）； - 从2开始，若当前数为素数，则将其所有倍数标记为合数（false）；
- 重复步骤2，直到遍历到给定范围的平方根。
以下是Java实现：
public static void sieveOfEratosthenes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, 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;
}
}
}
// 输出所有素数
for (int i = 2; i <= n; i++) {
if (isPrime[i]) System.out.print(i + " ");
}
}
优化点：
- 内层循环从
i*i开始，因为小于i*i的倍数已被更小的素数标记； - 可进一步优化为分段筛法，适用于极大范围的素数求解。
适用场景：适合求解连续范围内的所有素数，时间复杂度为O(n log log n),效率远高于试除法。
概率性算法：米勒-拉宾测试
对于极大数（如超过64位整数），确定性算法可能效率低下，此时可采用概率性算法，米勒-拉宾测试是一种高效的素性检验方法，通过多次随机测试降低误判概率,以下是简化实现：
public static boolean millerRabinTest(long n, int k) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0) return false;
// 分解n-1为d*2^s
long d = n - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
// 进行k次测试
Random rand = new Random();
for (int i = 0; i < k; i++) {
long a = 2 + rand.nextLong() % (n - 4);
long x = modPow(a, d, n);
if (x == 1 || x == n - 1) continue;
for (int j = 0; j < s - 1; j++) {
x = modPow(x, 2, n);
if (x == n - 1) break;
}
if (x != n - 1) return false;
}
return true;
}
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;
}
特点：
- 时间复杂度为O(k log³ n)，k为测试次数；
- 可通过调整k的值平衡准确性与效率。
适用场景：适用于大数素性检验,如密码学领域。
性能对比与选择建议
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 试除法 | O(√n) | O(1) | 单个数判断，小范围 |
| 埃拉托斯特尼筛法 | O(n log log n) | O(n) | 连续范围素数求解 |
| 米勒-拉宾测试 | O(k log³ n) | O(1) | 大数素性检验，概率性需求 |
实践建议：
- 若仅需判断单个数且数值较小（如小于10⁶），试除法足够高效；
- 若需求解1到n的所有素数，筛法是首选；
- 对于极大数或对性能要求极高的场景，可考虑米勒-拉宾测试结合确定性预处理。
Java中求解素数的方法多种多样，开发者需根据具体需求选择合适算法，基础试除法简单直观，筛法适合批量求解，而米勒-拉宾测试则为大数问题提供了高效解决方案，理解算法原理并优化实现细节，是提升编程能力的重要途径，在实际应用中，还可结合缓存、并行计算等技术进一步优化性能,以满足不同场景下的需求。
