为什么我编写的代码中，只有数字2147483647得不到正确的反馈结果？

Question

我编写了一个代码，用于判断一个数是否为质数。对于每个质数，它会打印该数+“是质数”，而对于非质数，它会打印该数=最小除数*最大除数。

但是，在处理最大的int值（2147483647）时，尽管它是一个质数，程序却打印出了第二行的结果……这是为什么呢？

以下是您提供的代码：

import java.util.Scanner;

public class FindDivisors2meth {
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        int n = myScanner.nextInt();
        boolean isPrime = true;
        int p = 2;
        while( p * p <= n && isPrime ) {
            if( n % p == 0) {
                isPrime = false;
            } else {
                p = p + 1;
            }
        }
        if( isPrime) {
            System.out.println(n + " is prime");
        } else {
            System.out.println(n + "=" + p + "*" + n/p);
        }
    }
}

Kerrek SB · Answer

当您尝试输入2147483647时，您的程序将其作为int类型处理，由于数据类型的限制，发生了溢出，导致了意外的行为。
您可以尝试将'int'改为'Long'，这样应该会返回“2147483647是质数”。

Programmer · Answer

您的问题在于数值溢出。数字在计算机中占用有限的位数。Java中的int类型为32位，因此，最大的正整数是2³² - 1，因为我们需要一半的空间来表示负数。

现在，您正在递增一个数，直到其平方小于或等于输入值且isPrime为false。但是，如果输入恰好是2³² - 1，则第一个条件永远不会成立。因此，最终p会超出int类型的边界，并逐渐递增到1，这时您的算法会错误地判断它不是质数。为了解决这个问题，您可以计算输入值的平方根，并将其作为循环限制条件，这样代码就能正常工作了。

Rob Napier · Answer

2147483647 是能够容纳在 Java 中 int 类型中的最大数值。实际上，int 并不意味着“任何整数”，而是指：一个能适应32位空间的有符号（采用二补数表示）整数。

关键在于，2³¹-1 是最大的正整数“边界”，而 -2³¹ 是最大的负整数“边界”。这些数值会发生溢出：

int x = 2147483647;
System.out.println(x == Integer.MAX_VALUE); // 输出为 true，表明 x 等于 int 的最大值
x++;
System.out.println(x); // 输出为 -2147483648，表示发生了溢出
System.out.println(x == Integer.MIN_VALUE); // 输出为 true，表明溢出后 x 成为了 int 的最小值
x--;
System.out.println(x); // 输出为 2147483647，恢复到原来的最大值

至关重要的是，当 n 是 int 能表示的最大值时，条件 p * p <= n 永远不可能为假，因为没有比它更大的数了。因此，在这种情况下，您的 while 循环会无休止地执行下去。最终经过大量循环之后，变量 p 达到 2147483647，然后进入下一次循环，此时 p 变为 -2147483648。继续循环很多次后（事实上，需要循环4294967293次），p 最终变为1。这时终于满足 n % p 等于0，于是 isPrime 被设置为 false，这是在这种情况下唯一能让循环结束的方法——通过令 isPrime 为 false，考虑到 p * p <= n 在此条件下无法为假（对于任何数 X，若 n 为 int 类型的最大值，则 X <= n 总是成立的，因为没有任何数能大于或等于已知的最大整数值）。

解决方案如下：

使用 long 类型代替。这会提供更多的存储空间；long 类型同样是整数类型，但占用64位，因此可以表示从 2⁶³-1 到 -2⁶³ 的数值范围，即大约18位数字大小。不过，如果输入恰好是 2⁶³-1，仍然会有问题，除非……你继续使用 .nextInt() 方法读取整数，但是将其 强制转换 为 long 类型存储。这样就避免了上述问题。
特殊处理这种情况。真正的问题在于 p*p 变为负数（因为结果超过 2³¹-1 时会发生溢出），所以找到那个使该条件成立的临界值（即大于 sqrt(2147483647) 的所有数），你可以在此临界值之上停止循环，或者当 p*p 大于 n 时也停止。
使用 BigInteger 类型。现在你的代码可以处理任意大小的输入，尽管与高效的质数查找算法相比，其运行速度将会极其缓慢。