素数的计算方法

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++) {
    ...
}

Answer 2

原因是，任何数字都不能除以大于它的一半的除数，并且大于1(当然，如果我们是在讨论整数的话)。

Answer 3

任何数字都不能被超过一半的数字整除。

例如，最后一个数字10是可除的。10不能与6、7、8或9整除。

这就是为什么要消除明显的不匹配，以提高算法的性能。