计算素数的方法

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