Java 代码高效判断质数124

在计算机科学中，判断质数是一项常见的任务。质数是只能被 1 和自身整除的正整数。在某些应用中，快速高效地识别质数至关重要，例如密码学和数据安全。

Java 提供了多种方法来判断质数。以下是一些最常用的方法：

朴素算法

朴素算法是对每个数字从 2 到 sqrt(n) 进行循环，查看它们是否能整除 n。如果任何数字整除 n，则 n 不是质数。```java
public static boolean isPrimeNaive(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i 0) {
if ((b & 1) != 0) {
result = (result * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return result;
}
```

米勒-拉宾素数判定法

米勒-拉宾素数判定法是一种比费马小定理更有效的概率算法。它基于以下事实：对于任何奇素数 n，存在一个称为“原根”的正整数 a，使得对于 1 ≤ k ≤ n-1，a^k mod n 等于 n-1 的某个幂。```java
public static boolean isPrimeMillerRabin(int n) {
if (n < 2) {
return false;
}
int s = 0;
int d = n-1;
while ((d & 1) == 0) {
s++;
d >>= 1;
}
for (int a : new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n % a == 0) {
return false;
}
long x = pow(a, d, n);
if (x == 1 || x == n-1) {
continue;
}
boolean isPrime = false;
for (int r = 1; r < s; r++) {
x = (x * x) % n;
if (x == n-1) {
isPrime = true;
break;
}
}
if (!isPrime) {
return false;
}
}
return true;
}
```