我不明白这个质数检查器背后的逻辑 (Java)

Question

我不明白这个数字检查器背后的逻辑，我想知道是否有人可以帮助我更好地理解它。

代码如下：

我会尽力对正在发生的事情发表评论，但我并不完全理解它。

//find prime numbers between 2 and 100

class PrimeNumberFinder {
    public static void main(String args[]) {

        int i, j; // declare the integer variables "i" and "j"
        boolean isPrime; // declare the Boolean variable is prime but do not assign value

        // create a for loop that starts at two and stops at 99.
        for (i=2; i < 100 ; i++) {
            isPrime = true; // I do not know why isPrime is set to true here.
            // This is where I get confused badly.. we give the "j" variable a value of two and check to see if it's less than whatever "i" divided by "j" is.             
            // If "i=2" then how would j (which is = 2) be less than or equal to i/j (2/2)? 

            for (j = 2; j <= i/j; j++)
                if ((i%j) == 0) isPrime = false; // If a certain number goes in evenly that isn't 1, or "i" itself, it isn't prime so we set the boolean to false

            if (isPrime) // if true print i
                System.out.println(i + " Is a prime number");


        }
    }
}

如您所见，第二个 for 循环及其中发生的几乎所有事情都让我感到困惑，尤其是 "j <= i/j"，因为对我来说 j 总是会变大……为什么 "j"甚至增加？你不能把它除以二然后确定它是否是素数吗？

非常感谢任何帮助，感谢您的阅读。

Answer 1

让我们逐行过一遍。

int i, j;
boolean isPrime;

我们从声明变量开始。没什么特别的。

for (i=2; i < 100; i++) {
    isPrime = true;

这里我们进入循环，基本上包含我们要检查的所有数字（这里：2 - 99）。我们还声明当前数字是素数（除非另有证明）。

    for (j = 2; j <= i/j; j++)
        if ((i%j) == 0) isPrime = false;

神奇的地方来了。我们将检查是否可以将当前数字 i 除以从 j == 2 到 i/j 的任何整数（i/j 最终只是一种奇特的写作方式 Math.sqrt(i)).那么，为什么直到那里？

好吧，假设我们有两个除数 a 和 b 使得 a * b = i。现在，如果除数 a 大于 i 的平方根，则另一个除数 b 将小于 i 的平方根。如果不是，那么 a * b > i 这是不可能的。

所以，如果我们能找到一个可以均分的情况，这明确意味着当前数字不是质数，我们将 isPrime 变量设置为 false.

    if (isPrime) // if true print i
        System.out.println(i + " Is a prime number");

}

所以，如果我们还有isPrime == true，说明当前的数字经受住了我们的考验，我们可以打印了。

两个进一步的改进；

一旦我们知道这个数不是质数，就没有必要检查任何额外的除数，所以我们想退出循环，因此 break; 可以添加声明。
2 是只有偶素数，所以你也可以在 j == 3 处开始第二个循环，并在每次执行后增加 2。然后，您必须单独考虑 i == 2 的情况。

我不明白这个质数检查器背后的逻辑 (Java)

I do not understand the logic behind this prime number checker (Java)

java

finder

numbers