为何2147483647作为唯一Int值，我的素数判断代码返回错误结果？

问题重现 #

你编写的素数判断逻辑中，当输入int类型最大值2147483647（本身是素数）时，代码错误地输出了非素数结果。

核心原因：整数溢出 #

问题出在循环条件p * p <= n上：

• 2147483647是int类型的最大值（即2^31 - 1），当循环中p增长到46341时，p * p的结果为2147488281，这个数值超出了int类型的取值范围，触发整数溢出。
• 在Java中，int溢出后会按二进制补码规则循环，结果变为负数。此时负数 <= 2147483647的判断恒为true，循环无法终止。
• 后续p会持续递增，直到p等于n时，n % p == 0的条件成立，isPrime被设为false，最终错误输出非素数格式。

修复方案 #

有两种常见方式避免溢出问题：

方案1：用long类型规避溢出 #

将p * p的计算转换为long类型，避免超出int范围：

while( (long)p * p <= n && isPrime )

方案2：替换循环条件为p <= n / p #

当p小于等于√n时，n / p必然大于等于p，用这个判断代替p*p <=n，完全避免乘法溢出：

while( p <= n / p && isPrime )

修复后的完整代码 #

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 <= n / p && 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);
        }
    }
}

内容的提问来源于stack exchange，提问作者Ofek Essenfeld