Largest Divisor of N (Excluding Itself)

Question

I'm trying to divide a list into sublists that are as large as possible. If the list can not be divided in such a way, I will handle it as needed, but I need get the largest number besides N itself that divides N evenly.

I wrote a really naive solution, but I feel like there should be maybe a formula or something to do this in constant time. My list are not that big, maximum size is 1000. This probably isn't the critical path, but is there a better algorithm?

public static int largestDivisor(int n){
   int divisor = 0;
   for (int i = 1; i <= n/2; i++)
       if (n % i == 0) 
           divisor = i;

   return divisor; 
}

Possible duplicate of [I need an optimal algorithm to find the largest divisor of a number N. Preferably in C++ or C#](http://stackoverflow.com/questions/3545259/i-need-an-optimal-algorithm-to-find-the-largest-divisor-of-a-number-n-preferabl) — , Jan 24 '17 at 18:10
Possible duplicate of [Java: get greatest common divisor](http://stackoverflow.com/questions/4009198/java-get-greatest-common-divisor) — MikaelF, Feb 01 '17 at 18:49

score 6 · Accepted Answer · edited May 23 '17 at 12:17

Iterate the values in reverse. Simply return the first one you find (it'll be the greatest). Something like,

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

Alternatively, you might make a slight improvement to @WillemVanOnsem's answer and start with odd values like;

public static int largestDivisor(int n) {
    if (n % 2 == 0) {
        return n / 2;
    }
    final int sqrtn = (int) Math.sqrt(n);
    for (int i = 3; i <= sqrtn; i += 2) {
        if (n % i == 0) {
            return n / i;
        }
    }
    return 1;
}

It's faster than the original, but not as fast as other methods. — D M, Jan 24 '17 at 18:04

Willem Van Onsem · Answer 2 · 2017-01-24T17:59:39.513

You know that if a is dividable by b, it is also dividable by a/b and the smaller b is, the larger is a/b, so once you have found the divisor, return n/divisor:

public static int largestDivisor(int n){
    for(int i = 2; i <= n/2; i++)
        if(n % i == 0) {
            return n/divisor;
        }
    }
    return 0; //or whatever you decide to return if there is no such divisor
}

This is also faster because:

divisors tend to become more rare the larger they get; and
you can already give up at sqrt(n).

So the most efficient approach would be:

public static int largestDivisor(int n){
    int sqrtn = (int) Math.sqrt(n);
    for(int i = 2; i <= sqrtn; i++)
        if(n % i == 0) {
            return n/divisor;
        }
    }
    return 0; 
}

score 1 · Answer 3 · answered Jan 24 '17 at 17:57

I don't know if you can do this in constant time, but you can certainly do it in less time than this.

Start with 2, and loop through all numbers, checking if n is divisible by that number. When you get to a number that divides n, then you can stop - your answer is n/i. If you get to the end and it still doesn't divide, then n is prime and the answer is just 1.

Instead of ending at n/2 if you don't find a divisor, you can end at √n with this method, which will reduce the big O.

Also, you could start with checking if it's divisible by 2, then go to 3 and only check the odd numbers from there. (If it was divisible by an even number, then it was divisible by 2.) That won't change the big O, but it should cut the processing time almost in half since you're only checking about half the divisors.

In fact, you could just check whether it's divisible by the prime numbers and skip any non-primes. The problem is that calculating which numbers are prime is more work than it would save, so unless you just happen to have a list of prime numbers handy that your program could use,it's probably not worth it. — D M, Jan 24 '17 at 18:00

Largest Divisor of N (Excluding Itself)

3 Answers3

Linked