java判断素数的方法有哪些

Java

小亿

2023-08-23 21:29:13

栏目: 编程语言

判断一个数是否为素数的常用方法有以下几种：

暴力法：从2开始逐个判断该数能否被整除，如果能被除以2至该数之前的任意数整除，则该数不是素数，否则是素数。

public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

优化暴力法：在暴力法的基础上，可以只判断到该数的平方根，因为如果一个数可以被大于其平方根的数整除，那么一定也可以被小于其平方根的数整除。

public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

Sieve of Eratosthenes（埃拉托斯特尼筛法）：首先创建一个长度为n+1的布尔数组，初始值都为true。然后从2开始，将其所有的倍数标记为false，直到n为止。最后，布尔数组中仍然为true的索引对应的数即为素数。

public static boolean[] sieveOfEratosthenes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
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;
}

以上是常用的判断素数的几种方法，可以根据具体的需求选择合适的方法。

java判断素数的方法有哪些

最新问答

相关标签