java - 计算素数的方法

我试图弄清楚这个Java方法是如何计算素数的，但是这让我感到困惑。

public static boolean isPrime(int number){
    for(int divisor =2; divisor <= number / 2; divisor++){
        if (number % divisor ==0){
            return false;
        }
    }
    return true;
}

如您在for循环的第二行所见，它显示的是divisor <= number /2而不是divisor <= number。谁能告诉我原因呢？

最佳答案

首先，如果您输入divisor <= number，则根本不会得到质数，因为每个数字都可以被整除。如果循环未在divisor变为number之前退出，则可以转到

number % divisor == 0

条件，然后返回false。

编写此代码的人观察到，一旦达到数值的一半，您就可以立即停止，因为如果在间隔(2..number/2)的下半部分没有找到除数，那么也就不会有除数超过一半的除数，因此您可以声明数字素数，而不会尝试其他候选除数失败。

但是，这并不是您可以做的最好的事情：可以使用更强的条件-您可以将divisor与number的平方根进行比较。之所以有效，是因为如果您没有小于或等于number的平方根的除数，那么在平方根的上方也将没有除数（考虑为什么这样做是个好主意）。

int stop = Math.sqrt(number);
for(int divisor = 2; divisor <= stop ; divisor++) {
    ...
}