程序找到素数。第2章自测schildt java初学者指南

Question

在第2章Schildt的Java初学者指南的自我测试中，有一个练习来编写一个程序，找到2到100之间的所有素数。

作者给出的正确答案如下：

class Prime {
    puЬlic static void main(String args[]) {
        int i, j;
        boolean isprime;
        for(i=2; i < 100; i++) {
            isprime = true;
            for (j=2; j <= i/j; j++)
                if((i%j) == 0) isprime = false;
            if (isprime)
                System.out.println(i +" - is a prime number."); 
        }
    }
}

我无法理解两件事

1）第二个FOR循环的条件：

j <= i/j;

这是寻找素数的某种数学算法吗？

我的条件版本看起来像

j < i;

2）如果在第二个循环的条件下放入i <= j而不是i < j，则程序的输出将为空。为什么？

谢谢你的帮助！

第二个问题的解释：

当我解决这个问题时，依赖于素数定义的“我的”版本，我的代码看起来像这样：

for(i=2; i < 100; i++) {
            isprime = true;
            for (j=2; j <= i; j++)
                if((i%j) == 0) isprime = false;
            if (isprime)
                System.out.println(i +" - is a prime number."); 
        }

注意第二个周期的条件：i <= j。少于或等于

如果你依赖于素数的“我的”定义，那么条件中的等号应该是。

尝试运行该程序。输出将为空。

但如果条件删除等号for (j=2; j < i; j++)，程序将正常工作。

是什么原因？

Answer 1

让我们关注这些qazxsw poi循环。

for

第一个循环遍历您要测试的所有数字。很容易理解，它只是告诉“我想对2到100之间的所有数字执行以下测试”。

        for(i=2; i < 100; i++) {
            isprime = true;
            for (j=2; j <= i/j; j++)
                if((i%j) == О) isprime = false;
            if (isprime)
                System.out.println(i +" - is a prime number."); 
        }

现在这个循环是纯数学。数学上，素数：

是一个大于1的自然数，不能通过乘以两个较小的自然数来形成。

（来源：维基百科）

因此，你遍历所有数字，乘以，形成i。

但你真的需要吗？例如，如果i = 3 * 25，您是否需要一直迭代到25才能知道我不是素数？

答案显然是否定的，因为在测试j = 3之后，你已经知道我是复合的。

在数学上，存在多种算法来检查数字是素数还是复数。但是，合理正确的方法是检查数字是否是

for (j=2; j <= i/j; j++)
    if((i%j) == О) isprime = false;

的倍数。您正在执行此的四舍五入版本。

由于上述原因，检查2和i之间的所有数字是多余的。

编辑：回答2）

使用时

any number between 2 and its own square root

你告诉编译器在

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

上执行测试后停止循环。当然，当j等于i时，（i％j）== 0总是求值为真。

在非信息术语中，您正在检查数字是否由任何数字组成，不包括1，包括其本身，而您应检查它是否由任何数字组成，不包括1和它本身。

这是由于Java实现j==i循环的方式：for