寻找质数的程序。第二章自测schildt java 新手指南

Question

在 Schildt 的 Java 初学者指南第 2 章的自测中，有一个练习可以编写一个程序来查找 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，那么程序的输出将为空。为什么？

感谢您的帮助！

第二个问题的解释：

当我解决这个问题时，依靠 "my" 版本的质数定义，我的代码如下所示：

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."); 
        }

注意第二个循环的情况：我 <= j。小于等于

如果你依赖"my"定义素数，那么条件中的等号应该是。

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

但是如果条件去掉等号for (j=2; j < i; j++)，程序会正常运行。

这是什么原因？

Answer 1

让我们关注这些 for 循环。

        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."); 
        }

第一个循环遍历所有要测试的数字。很容易理解，它只是告诉 "I want to perform the following test on all numbers from 2 to 100".

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

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

is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

（来源：维基百科）

因此，您遍历所有相乘后将形成 i 的数字。

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

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

在数学上，存在多种算法来检查一个数是质数还是合数。但合理正确的方法是检查一个数是否是 any number between 2 and its own square root 的倍数。您正在执行此操作的汇总版本。

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

编辑：回答 2)

使用时

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

您是在告诉编译器在对 j==i 执行测试后停止循环 。当然，当 j 等于 i 时，(i%j) == 0 总是计算为真。

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

这是由于 Java 实现 for 循环的方式：they stop when the middle condition evaluates to false.

寻找质数的程序。第二章自测schildt java 新手指南

Program to find Prime numbers. Chapter 2 Self test schildt java beginner's guide

java

primes

寻找质数的程序。第二章 自测schildt java 新手指南

Program to find Prime numbers. Chapter 2 Self test schildt java beginner's guide

java

primes

寻找质数的程序。第二章自测schildt java 新手指南