如何找到最接近数字平方根的除数？Java程序结果不符合预期

你的现有代码逻辑存在问题：它从n/2开始向下遍历，找到第一个能整除n的数就直接返回，这会返回n的最大除数（除n本身外），比如输入42时返回21，这显然不符合“最接近平方根”的需求。

正确思路 #

最接近平方根的除数一定在n的平方根附近，所以我们可以：

• 先计算n的平方根sqrtN
• 从sqrtN开始向下遍历，找到第一个能整除n的数i，对应的另一个除数是n/i，这两个数就是最接近平方根的一对
• 若n是质数，遍历结束后返回1或n均可

修正后的代码 #

基础版本（返回较小的那个接近平方根的除数）

public static int closestDivisor(int n) {
    if (n <= 1) {
        return n;
    }
    int sqrtN = (int) Math.sqrt(n);
    // 从平方根位置向下查找第一个能整除n的数
    for (int i = sqrtN; i >= 2; i--) {
        if (n % i == 0) {
            return i;
        }
    }
    // 质数情况，返回1
    return 1;
}

测试closestDivisor(42)时，sqrt(42)≈6.48，遍历从6开始，42%6==0，直接返回6，符合预期。

进阶版本（返回最接近平方根的那个除数）

如果需要严格返回距离平方根更近的除数，可以添加比较逻辑：

public static int closestDivisor(int n) {
    if (n <= 1) {
        return n;
    }
    double sqrtN = Math.sqrt(n);
    int floorSqrt = (int) sqrtN;
    for (int i = floorSqrt; i >= 2; i--) {
        if (n % i == 0) {
            int otherDivisor = n / i;
            // 比较两个除数与平方根的距离
            if (Math.abs(i - sqrtN) <= Math.abs(otherDivisor - sqrtN)) {
                return i;
            } else {
                return otherDivisor;
            }
        }
    }
    return 1;
}

比如输入42时，6与平方根的距离（≈0.48）小于7的距离（≈0.52），返回6；若输入15（sqrt≈3.87），3的距离更小，返回3。

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