I’ve been trying to make a program that gives me a divisor of a number n that is closest to its square root.

I’ve tried to accomplish this by using this program:

public static int closestDivisor(int n) {
    for (int i = n/ 2; i >= 2; i--) {
        if (n % i == 0) {
            return i;
        }
    }
    return 1;
}

However, when I run this:

System.out.println(closestDivisor(42));

I get 21 when expecting either 6 or 7 because those are the closest divisors of 42.

>Solution :

if (i < 4) return 1;

int divisor = 1;
for (int i = 2; i < n; i++) {
    if (i * i == n) return i;
    if (i * i < n && n % i == 0) divisor = i;
    if (i * i > n) return divisor;
}

return -1; // never executed, unreachable

This code should return the largest number which evenly divides n and which is less than or equal to the square root of n.

You can then look at this number, let’s call it answer, and n/answer, and one of those is guaranteed to be the factor of n closest to the square root of n. To see which is which, we can compare n – answer*answer and (n/answer * n/answer) – n, and see which is smaller; if the first difference is smaller then answer is closer to n, otherwise n/answer is closer to n.