java - 我不明白这个素数检查器(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 ，说明当前的数字通过了我们的测试，可以打印出来。

两项进一步改进；

1. 一旦我们知道该数字不是素数，就不需要检查任何额外的除数，所以我们想退出循环，因此 break;可以添加声明。
2. 2是唯一偶素数，所以你也可以从 j == 3 开始第二个循环并增加2每次执行后。然后，您必须考虑 i == 2 时的情况。分别。