java - 素数的计算方法

Question

我想弄清楚这个 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 .谁能告诉我这是为什么？

Answer 1

首先，如果你输入 divisor <= number ，你根本不会得到质数，因为每个数都可以被自身整除。如果循环在 divisor 之前没有退出变成 number , 你会得到

number % divisor == 0

条件，返回false .

编写此代码的人观察到，您可以在达到一半数字后立即停止，因为如果您没有在区间 (2..number/2) 的下半部分找到除数，也不会有超过数字一半的除数，因此您可以声明数字质数而无需尝试其余候选除数，但未成功。

但是，这不是您能做的最好的:可以使用更强的条件 - 您可以比较 divisor到 number 的平方根.这是有效的，因为如果你没有一个小于或等于数字平方根的除数，那么也不会有大于平方根的除数(最好想想为什么会这样)。

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