16. Proper divisors

An obvious method for finding the proper divisors of the number N is to consider all of the values between 1 and N/2 and see which ones divide into N evenly. The following method takes this approach:

// Examine values between 1 and number / 2.
private List<long> Method1(long number)
{
    checked
    {
        List<long> divisors = new List<long>();
        long limit = number / 2;
        for (long factor = 1; factor <= limit; factor++)
        {
            if (number % factor == 0)
                divisors.Add(factor);
        }
        return divisors;
    }
}

This method is straightforward, but it can be slow if the number is large. For example, if the number is 10 billion, then the method must examine 5 billion values.

In contrast, the prime factoring algorithms described earlier in this chapter only needed to examine values up to the square root of the number. For example, if the number is 10 billion, then its square root is 100,000, which is 50,000 times smaller than the 5 billion numbers examined by the preceding code.

The reason why prime factoring code only needs to examine values up to the square root of the number is that each larger factor would be paired with a smaller factor. If the number N = p × q and p > , then q < . If we only examine values up to , we won't find p, but we will find q.

We can use similar logic when we look for divisors. Continuing from the previous example, if we only examine values up to , we still won't find p. However, when we find q, we can use it to calculate p because N = p × q. That gives us the following method for finding divisors:

// Examine values between 2 and Sqrt(number).
private List<long> GetProperDivisors(long number)
{
    checked
    {
        List<long> divisors = new List<long>();
        divisors.Add(1);
        long limit = (long)Math.Sqrt(number);
        for (long divisor = 2; divisor <= limit; divisor++)
        {
            if (number % divisor == 0)
            {
                divisors.Add(divisor);
                long divisor2 = number / divisor;
                if (divisor != divisor2) divisors.Add(divisor2);
            }
        }
        divisors.Sort();
        return divisors;
    }
}

This method creates the divisors list and adds 1 to it. It then loops over values between 2 and the square root of the number.

If a value divides evenly into the number, then it is a divisor, so the method adds it to the divisors list.

The number divided by the divisor is also a divisor, so the method also adds it to the list. The only trick here is that the two divisors might be the same if the number is a perfect square. For example, if the number is 49, then the method will find the two divisors 7 and 49/7 = 7. The method checks that the second divisor is different from the first before adding it to the list.

Because the method adds small and large divisors in pairs, the final list is not sorted, so the method sorts the list before returning it.

The following screenshot shows the ProperDivisors example solution finding the 71 proper divisors of the number 123,456,780. You can see that the second method is much faster than the first:

The trick to this solution was to think about the earlier technique used by the factoring algorithms and then find a way to apply a similar technique to this problem. Examining values only up to the square root of the number saved a huge amount of time.

Download the ProperDivisors example solution to see additional details.