Java判断平方自由数的代码报除零错误，如何高效计算long类型平方？

错误原因 #

你遇到的除零错误本质是int类型整数溢出导致的：

• Java中int是32位有符号整数，取值范围为-2^31 ~ 2^31-1（即-2147483648 ~ 2147483647）
• 你的循环变量i是int类型，当i的值大于46340时，i*i的结果就会超过int的最大值，发生溢出：溢出后结果会绕回为负数，当i增长到65536时，i*i = 2^32，对应的32位有符号整数补码表示恰好为0，此时执行number % 0就会抛出除零错误。

修复方案 #

基础修复版 #

直接调整变量类型和循环边界即可解决问题，同时性能会有量级提升：

static boolean squarefree(long number) {
    // 小于2的整数默认无平方因子
    if (number < 2) {
        return true;
    }
    // 循环只需到sqrt(number)即可，不需要遍历到原数
    for (long i = 2; i * i <= number; i++) {
        if (number % (i * i) == 0) {
            return false;
        }
    }
    return true;
}

核心优化点：

1. 把循环变量i的类型改为long，避免乘法溢出；如果坚持用int类型，计算平方时先强转为long即可：(long)i * i
2. 循环终止条件从i <= number改为i*i <= number：只要存在大于等于2的平方因子，必然有一个因子小于等于sqrt(number)，1e13的平方根仅为约316万，循环次数直接从1e13次降到3e6次，性能提升巨大。

进阶优化版 #

单独处理偶因子后只遍历奇数，性能再提升一倍：

static boolean squarefree(long number) {
    if (number < 2) return true;
    // 单独判断2的平方因子
    if (number % 4 == 0) return false;
    // 后续只需要遍历奇数
    for (long i = 3; i * i <= number; i += 2) {
        if (number % (i * i) == 0) {
            return false;
        }
    }
    return true;
}

long类型平方计算注意事项 #

你不用Math.pow的选择是正确的：Math.pow是基于浮点运算实现的，不仅性能比整数乘法低，对于大整数还会出现精度丢失问题，完全不适合整数平方计算。
计算long类型平方时，要保证至少有一个操作数是long类型再执行乘法：如果两个操作数都是int，会先按int规则计算再强转long，此时溢出已经发生，正确写法是(long)a * b，不要写成(long)(a*b)。1e13以内的数值计算平方完全在long的取值范围内（long最大可支持到9e18），不会出现溢出问题。

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