Java 素数判断的 3 种高效方法382

素数，也称为质数，是仅被 1 和自身整除的自然数。在计算机科学中，素数判断是一个常见的任务，本文将介绍 Java 中判断素数的三种高效方法。

1. 试除法

试除法是最简单的素数判断方法。其思想是逐个尝试从 2 到 sqrt(n) 的数，如果 n 能被其中任何一个数整除，则 n 不是素数；否则，n 是素数。```java
public static boolean isPrimeTrialDivision(int n) {
if (n 1;
x = (x * x) % mod;
}
return res;
}
```

3. 米勒-拉宾素性检验

米勒-拉宾素性检验是一种比费马小定理更有效的素数判断算法。它基于以下定理：如果 n 是一个合成数，那么存在一个整数 a（称为见证者），使得 a^(n-1) ≡ 1 (mod n) 不成立。我们可以随机选择多个见证者来判断一个数是否为素数。```java
public static boolean isPrimeMillerRabin(int n) {
if (n >= 1;
}
for (int a : new int[]{2, 7, 61}) {
if (witness(a, d, s, n)) return false;
}
return true;
}
private static boolean witness(int a, int d, int s, int n) {
long x = power(a, d, n);
if (x == 1 || x == n - 1) return false;
for (int r = 1; r < s; r++) {
x = (x * x) % n;
if (x == n - 1) return false;
}
return true;
}
```

性能比较

这三种方法的性能差异很大。试除法是最慢的，因为它需要遍历所有小于 sqrt(n) 的数。费马小定理比试除法快，但仍然比米勒-拉宾素性检验慢。米勒-拉宾素性检验是最快的，但它可能会产生错误的负面结果（即错误地认为一个合成数是素数）。

选择建议

在实践中，使用米勒-拉宾素性检验通常是判断大数素数的最佳选择。对于较小的数，费马小定理可能是一个更简单的选择。试除法一般不建议使用，只有在需要判断非常小的数时才使用。

2024-11-14

上一篇：Java 对话框：在您的应用程序中显示交互式弹出窗口

下一篇：使用 Java 连接 Oracle 数据库