java - 在 java 中编写 isPrime 函数并使用 Math.sqrt

Question

在 Java 中编写 isPrime 函数以返回布尔值时，我看到了很多人们在 for 循环中使用 Math.sqrt(number) 的示例。有人可以解释为什么这个函数在 for 循环中做了什么吗？我附上了一个例子供参考。谢谢！

    public boolean isPrime(int n) {
       if (n <= 1) {
           return false;
       }
       for (int i = 2; i < Math.sqrt(n); i++) {
           if (n % i == 0) {
               return false;
           }
       }
       return true;
    }

Answer 1

你怎么知道一个数 n 是不是素数？第一个策略是测试从 2 到 (n-1) 的所有数字。对于每个值 i，检查 n 是否除以 i。如果你找到这样的 ai，那么 n 不是素数。

但是你真的需要测试所有的值吗？不，一旦您达到 n 的平方根，您将测试相同的“对”值。换句话说， sqrt 可以限制要完成的测试数量，从而提高性能。

Answer 2

如果一个数不是素数，它可以分解为两个因式 f1 和 f2

如果 f1 和 f2 > 数字的 sqrt，则 f1*f2 将 > 数字。因此，至少其中一个因素必须 <= 到数字的 sqrt。要查看一个数字是否真的是素数，我们只需要测试 <= 到 sqrt 的因子。