java - 在 Java 中查找素数

Question

我遇到了一个 Java 程序，它可以查找给定的数字是否是素数。这是代码。

class FindPrime {
    public static void main(String args[]) {
        int num;
        boolean isPrime;
        num = 14;

        if (num < 2) 
          isPrime = false;
        else 
          isPrime = true;

        for (int i = 2; i <= num / i; i++) {
            if ((num % i) == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) 
          System.out.println("Prime");
        else 
          System.out.println("Not Prime");
    }
}

这里，我不确定为什么在for循环中使用条件i <= num/i。有人可以帮我解释一下吗？

Answer 1

限制条件i <= num / i是性能优化:

给定例如num = 11和i = 3 ，到目前为止，我们已经检查了 11 是否可以被 2 整除(否)，现在正在移动到 3，我们应该检查它，答案是否定的，它不能被 3 整除。现在我们正在移动到 4，我们是否还应该检查11能被它整除吗？这样的除法将得到 2.75，这个值小于我们已经检查过的 3。任何更高 i将产生更小的值，我们已经检查过所有这些值，因此没有必要进一步检查。我们现在知道答案了。