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.

CodePudding user response：

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.

CodePudding user response：

Here is one way.

• First, return -1 if the candidate is < 0 or 1 if < 4
• If n is a perfect square, return the square root.

Now inside the loop, Start from the square root and work outwards checking both sides of the square root for divisibility.

• The default divisor is initialized to -1.
• As the condition is evaluated either i divides n and i is returned via divisor
• Otherwise k divides n and k is returned via divisor.

public static int closestDivisor(int n) {
    if (n < 4) {
        return n < 0 ? -1 : 1;
    }
    int v = (int)Math.sqrt(n);
    int divisor = v;
    
    if (v * v == n) {
        return v;
    }
    for (int i = (int) v, k = i; i >= 1; i--, k  ) {
        if ( n % (divisor = i) == 0
                || (n % (divisor = k) == 0)) {
            break;
        }
    }
    return divisor;
}

CodePudding user response：

public static int closestDivisor(int n) {
    if(n==1)
        return 1;
    int divisor = n;
    while (divisor > 1) {
        int temp = n % divisor;
        n = divisor;
        divisor = temp;
    }
    return n == 1 ? 1 : n/divisor;
}

Try something like this