2

下面是我用 Java 制作的第一个程序（在 Internet 的帮助下）。它是一个检查给定整数是否为素数并提示用户反馈的程序。如果用户输入不是整数，则输出它不是整数。后者也发生在输入大整数时。这是代码：

import java.util.Scanner;

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

        try {
            System.out.println("Enter an Integer: ");
            Scanner sc = new Scanner(System.in);

            int i; 
            int number = Integer.parseInt(sc.nextLine());

        // 1 and numbers smaller than 1 are not prime
            for (i = 1; number <= i;) {
                System.out.println("NOT a prime!");
                break;
            }

        // Number is not prime if the remainder of a division (modulus) is 0
            for (i = 2; i < number; i++) {  
                int n = number % i;         
                if (n == 0) {                 
                    System.out.println("NOT a prime!");
                    break;
                }  
            }

        // I do not understand why the if-statement below works.
            if(i == number) { 
                System.out.println("YES! PRIME!");
            }
        }

        catch(NumberFormatException nfe) {
            System.out.println("Not an integer!");
        }

    }
}

该程序完成了他的工作，但我不知道为什么带有 if 语句的部分有效。“i == number”怎么可能给出真值（当你输入一个素数时它会打印出“YES！PRIME”）？局部变量 i 在 for 循环中递增，但 if 语句在 for 循环之外。

/edit下面的段落是胡说八道，正如Jim Lewis 指出的那样
现在考虑一下，我能想到的唯一原因是因为 == 运算符检查 i-'object' 和 number-'object' 是否属于指向相同的“类型”（即，引用相同的对象）。由于它们都属于原始整数类型，因此该程序捕获整数（其他输入抛出 NumberFormatException 被捕获并输出“非整数”）。素数通过第一个 for 循环，然后神奇的 if 语句给出“true”，并打印出“YES！PRIME！”。

我在正确的轨道上吗？

我通过删除神奇的 if 语句并将其更改为 if-else 语句来改进该程序：（/edit修复了代码问题，感谢ajb 的回答）

boolean factorFound = false;            
for (i = 2; i < Math.sqrt(number) + 1; i++) {
    int n = number % i;
    if (n == 0) {
        factorFound = false;
        break;
    }  
    else {
        factorFound = true; 
    }
}
if(factorFound == false) System.out.println("NOT a prime!");
if(factorFound == true) System.out.println("YES! PRIME!");

通过只增加输入数字的平方根，计算时间得到改善（我知道只检查奇数或使用AKS Primality Test可以进一步改进，但这不是重点）。

我的主要问题是为什么我不能以同样的方式提高第一个程序（使用神奇的 if 语句）的效率。当我在第一个程序中像这样“（i = 2; i < Math.sqrt（number）+ 1; i++）”增强for循环时，它不再打印出“YES！PRIME！” 当你输入一个素数时。它给出一个空白。即使我之前的解释是正确的——它可能不是——也没有解释。

你可以启发我。

解答：int i 超出了 for 循环的范围，并且在多次通过 for 循环直到 number 之后， i 的值将达到值 number，当我们可以确定它是一个 prime 时。此外，在检查消失的“YES！PRIME！”之后 再次声明事实证明，实际上可以将 if 语句和 for 循环中的数字更改为 ( Math.sqrt(number) + 1 ) 并具有工作代码。所以这个问题是基于一个错误的前提。

4

2 回答 2

2

i在循环之外声明for，因此它的值仍在范围内并且在循环结束后可用（与比较数据类型或类似的事情无关！）。

如果没有找到除数，则i < number循环条件最终将失败，并且i == number. （如果循环找到一个除数并命中该break语句，则该条件不再成立）。

当您进行sqrt优化时，循环的结束条件发生了变化，因此i == number循环退出后不再成立，即使数字是素数。

在我看来，显式设置一个标志（例如isPrime=0，在跳出循环之前）然后检查该标志而不是查看循环变量来查看循环是否完成会更清楚。

于 2013-08-22T22:37:54.023 回答
1

// 我不明白为什么下面的 if 语句有效

解释：因为 i 一直递增直到等于 number。如果您在 sqrt(number) 处停止，则 if 语句将始终失败。

顺便说一句，我不喜欢将平方根与整数一起使用。我更喜欢 isPrime 函数：

        if (number < 2) return false;
        if (number > 2 && number % 2 == 0) return false;
        for (int i = 3; i * i <= number; i = i + 2)
            if (number % i == 0) return false;
        return true;
于 2013-08-22T22:30:34.863 回答