为什么2147483647是唯一一个我写的代码没有得到正确反馈的Int？

Question

我编写了一个代码来查找一个数字是否是质数。 对于每个质数，它打印数字 + 是质数 对于每个非素数，它打印数字=最低除数*最高除数

仅对于最大的整数（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);
        }
    }

}

Answer 1

当您尝试输入 2147483647 时，您的程序将其视为 int，并且由于数据类型的限制，它会溢出，从而导致意外行为。 你可以尝试用“Long”代替“int”，它会返回 2147483647 是素数。 :)

Answer 2

2147483647 是

int

中可能容纳的最大数字。你看，

int

并不意味着“任何整数”。它实际上意味着：一个适合 32 位的整数 - 将其视为有符号（用 2 的补码表示）数。

结果是，2^31-1是“适合”的最大正数，-2^31是“适合”的最大负数。这些数字环绕：

int x = 2147483647;
System.out.println(x == Integer.MAX_VALUE); // true
x++;
System.out.println(x); // -2147483648
System.out.println(x == Integer.MIN_VALUE); // true
x--;
System.out.println(x); // 2147483647

至关重要的是，

p * p <= n

永远不会为假，因为 n 是最大可能的整数，因此，没有数字可以大于它。因此，您的

while

循环将永远运行，最终，经过大量循环后，

p

的值达到 2147483647。此时您又循环一次，现在 p 为 -2147483648。你继续循环更多，最终（事实上，在 4294967293 次之后！），

p

最终变成 1，现在最终

n % p

确实是

0

，所以，

isPrime

设置为 false，这就是如何你的循环结束 - 唯一的方法是，通过

isPrime

为假，考虑到

p * p <= n

不能为假（

X <= n

对于任何 X，其中

n

是最大 int 值永远不会为假，想想它。一个数字怎么可能不“小于或等于”现有的最大数字）？

解决方案

1. 请使用

   long

   代替。这为你赢得了一些空间； long 是 64 位，但其他方面相同，因此最高可达 2^63-1，最低可达 -2^63，即大约 18 位数字。如果有人输入正好 2^63-1，您仍然会遇到问题，除非..您继续使用

   .nextInt()

   ，但 将其分配给 long

   。现在你就没有这个问题了！

2. 特殊情况。这里真正的问题是

   p*p

    变为负数（因为任何高于 2^31-1 的结果都会“循环”），因此，找到该值为真（它是大于 SQRT(2147483647) 的任何数字 - 其中你可以在计算器上运行）） - 如果 p 高于 

   或 如果 p*p

    高于 n，你可以停止。

3. 使用

   BigInteger

   ，现在你的代码可以处理任何大小的输入，但是，与高效的素数查找器相比，它会非常慢。

Answer 3

您的问题是号码溢出。您的数字占用有限的位数。 java int 是 32 位的，即最大数是 2^16 - 1，因为我们需要一半的空间来表示负数。

现在，您正在递增一个数字，直到其平方小于或等于您的输入并且

isPrime

 为 false。但是，如果您的输入恰好是 2^16 - 1，那么第一个标准将永远不会成立。因此，你最终会让 

p

 溢出 

int

 边界，并缓慢但肯定地增加它直到它为 1，然后你的算法将声称它不是素数。相反，计算输入的平方根并将其用作循环的限制，然后它就会起作用。