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;
        }
开发者_如何学运维

First thought you 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.

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;
    }

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

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).

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.

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.

Find the first prime which divides the number N.
Let's say that prime is d.
Divide N by d.
This is the required result that you want.

Java implementation of the solution:

static int highestDivisor(int n) {
    if ((n & 1) == 0)
        return n / 2;
    int i = 3;
    while (i * i <= n) {
        if (n % i == 0) {
            return n / i;
        }
        i = i + 2;
    }
    return 1;
}

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... :)

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.

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.

A solution if you know the smallest divisor is to apply the following formula:

largest_d = N - N % smallest_d

where N is the number whose largest divisor you're looking for.

def largest_divisor(N, smallest_divisor):
   return N - N % smallest_divisor

This code with a random big number (N = 94e15) and a random big divisor (divisor = 21e3) finished running the program in Python in 0.000740051269531 s.

Hope this helps.