Java中实现判断质数函数的方法
在Java中判断质数的最基本的方法是遍历从2到n-1，判断n是否能够被这些数整除。若没有数能够整除n，那么n就是质数；否则就不是质数。这种方法的时间复杂度为O(n)，由于需要遍历n-2个数，所以需要较长的时间。
优化方法1
优化方法1是只判断从2到n/2，因为如果一个数n不能被2到n/2之间的数整除，那么n肯定不会被n/2到n-1之间的数整除。时间复杂度为O(n/2)，缩短了一半的时间。
public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= n / 2; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
优化方法2
优化方法2是只判断从2到√n，因为如果一个数n不能被2到√n之间的数整除，那么n肯定不会被√n到n-1之间的数整除。时间复杂度为O(√n)，缩短了更多的时间。
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;
}
优化方法3
优化方法3是利用质数的性质，即如果一个数n不是质数，那么n一定能够被2到n/2之间的某个质数整除。所以只需要判断从2到√n之间的质数是否能够整除n即可。
public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (isPrime(i) && n % i == 0) {
return false;
}
}
return true;
}
private 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;
}
总结
以上是Java实现判断质数函数的三种方法。其中优化方法1、2、3对程序执行时间都有一定的优化，但是优化方法3需要使用到递归，可能会增加程序的复杂度。根据具体的需求和场景，可以选择不同的实现方式。