I need an optimal algorithm to find the largest divisor of a number N. Preferably in C++ or C#

Question

I am currently using the following code but its very slow for large numbers

        static int divisor(int number)
        {
            int i;
            for (i = number / 2; i >= 1; i--)
            {
                if (number % i == 0)
                {
                    break;
                }
            }
            return i;
        }

Answer 1

First thought -yYou can find the smallest divisor d (not equal to 1 of course), then N/d will be the largest divisor you're looking for.

For example if N is divisible by 3 then you'll need 2 iterations to find the answer - in your case it would be about N/6 iterations.

Edit: To further improve your algorithm you can iterate through odd numbers only (after checking if you number is even) or, even better, if you have the list of primes pre-calculated then you can iterate through them only because smallest divisor is obviously is a prime number.

Answer 2

In order to limit your search space, you should start at 2 and work up to the square root of the number. There are far more numbers (in a finite search space) divisible by 2 than by 27 so you're more likely to get a low divisor than a high one, statistically speaking.

You'll find a big difference when using the square root, rather than half the value, when you processing (for example) 1,000,000. The difference is between a search space of 500,000 for your method and 1,000 for the square root method is considerable.

Another advantage is to halve the search space right at the front by discounting multiples of two. Then, when you have your lowest divisor, the highest one is simply the number divided by that.

Pseudocode:

if n % 2 == 0:              # Halve search space straight up.
    print n / 2
else:
    i = 3                   # Start at 3.
    while i * i <= n:       # Or use i <= sqrt(n), provided sqrt is calc'ed once
        if n % i  == 0:
            print n / i     # If multiple, get opposite number, print and stop
            break
        i = i + 2           # Only need to process odd numbers

Answer 3

Don't know if it's the optimal solution but you'd probably be better starting at 2 then going upwards such as:

  static int divisor(int number)
    {
        int i;
        for (i = 2; i <sqrt(number); i++)
        {
            if (number % i == 0)
            {
                break;
            }
        }
        return number/i;
    }

EDIT

to get it to work with primes as well:

 static int divisor(int number)
    {
        int i;
        for (i = 2; i <=sqrt(number); i++)
        {
            if (number % i == 0)
            {
                return number/i;
            }
        }
        return 1;
    }

Answer 4

Optimization: An odd number can't have even number as largest divisor. Use this filter on number early. So if odd number is given.

• First do division with 2.

• Then decrement i by 2 everytime in loop

This is will improve speed for odd numbers.

Answer 5

A huge optimization (not sure if it's completely optimal - you'd have to ask a mathematician for that) is to search upwards using only prime numbers. As Vladimir and Bunnit said, it is better to search upwards, because you'll find it to be much faster. Then, return the inverse (number / i). However, if you've already tried 2 and come up dry, there is no point in trying 4 or 6. Similarly, if you've tried 3, there's no point in trying 6 or 9.

So, if time of running is a big concern, you could have a list of the first 100 primes hard coded in your program. Test each of them. If you don't find an answer by then, then you could just increment by 2 (skipping even numbers).

Answer 6

You've basically hit the "factorization of large numbers" problem, which is the basis of today's Public Key encryption and is known (or hoped) to be a computationally hard problem. I indeed hope that you will not find a much better solution, otherwise the whole security infrastructure of the world will collapse... :)

Answer 7

One of the industry standard methods for finding factors of large numbers is the Quadratic Sieve algorithm.

Have a read of this:

http://en.wikipedia.org/wiki/Quadratic_sieve

P.S. you should also consider how big your numbers are. Different factorisation algorithms tend to perform well for a certain size, and not for others. As noted in the QS wiki article, this method is generally the fastest for numbers less than about 100 decimal digits.

Answer 8

Have a look here :- http://programmingpraxis.com/contents/themes/#Prime%20Numbers

Programming Praxis regularly sets programming challenges for people to solve for a bit of fun on a Friday lunchtime. This particular problem crops up a lot and there are several well known algorithms for solving it illustrated with code.

Answer 9

Some additional optimizations:

1.  If even then divisable by 2.
2.  If the sum of the digits is divisable by 3, then number is divisble by 3 (ie 78 = 7 + 8 = 15 = 1 + 5 = 6 which is divisable by 3)
3.  If it ends in 0 or 5 it is divisable by 5

Gordon.

Answer 10

The best algorithm will depend on how huge your numbers will really be.

This problem is basically as hard as factoring integers - if have some factoring algorithm, it will be rather easy to use it to construct the greatest non-trivial divisor. Again, which of all the known factoring algorithms you employ for a number should depend on its 'hugeness', as for different scales these fancy algorithms will likely have different performances.

You will probably find several (maybe different) answers to your question in good books on cryptography, algorithmics and computational number theory.

Again, depending on your scale, it might even be an option to simple precompute a large list a prime numbers, save it, and then given an input number search within this list for the smallest divisor - which will immediately have the greatest divisor pop up, too.