C# Code to Find all Divisors of an Integer

Question

I made this so I can feed it integers and return an array with all the divisors of that integer. I put checks in in case the integer is less than 2. Order of integers in the array must be smallest to largest. The code works. What I need is to optimize this code to be as fast as possible. Right now on an online IDE I am getting around 40ms combined against the given test. I need to trim this down as much as possible.

using System.Collections.Generic;

public class Divisors
{
    public static bool IsPrime(int n)
    {
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        for (int x = 3; x * x <= n; x += 2)
            if (n % x == 0)
                return false;

        return true;
    }

    public static int[] GetDivisors(int n)
    {
        List<int> divisors = new List<int>();

        if (n < 2)
        {
            return null;
        }
        else if (IsPrime(n))
        {
            return null;
        }
        else
        {
            for (int i = 2; i < n; i++)
                if (n % i == 0)
                    divisors.Add(i);
        }

        return divisors.ToArray();
    }
}

namespace Solution 
{
  using NUnit.Framework;
  using System;

  [TestFixture]
  public class SolutionTest
  {
    [Test]
    public void SampleTest()
    {
      Assert.AreEqual(new int[] {3, 5}, Divisors.Divisors(15));
      Assert.AreEqual(new int[] {2, 4, 8}, Divisors.Divisors(16));
      Assert.AreEqual(new int[] {11, 23}, Divisors.Divisors(253));
      Assert.AreEqual(new int[] {2, 3, 4, 6, 8, 12}, Divisors.Divisors(24));
    }
  }
}

Answer 1

Style

As far as style goes, your code looks clean and readable, and follows the conventions, so good job for that.

You may want to include documentation comments with \\\ four your class and methods. Although the method names are descriptive enough in this rather simple case, it is a good habit to take on.

Tests

It's nice you use a test framework to test your class. However, the methods name don't match (Divisors vs GetDivisors) and comparing arrays doesn't work that way.

You could also benefit from including more tests for edge cases . What if the given argument is prime (since you make it a special case)? What if it is int.MaxValue? What if it is 0? What if it is negative?

Make your class static

Your Divisors class only has static methods. As such, it should be a static class. I might help the compiler with optimizations and can improve performance a little.

Unexpected behavior

As far as I know, 1 and n are always divisors of n, yet they are omitted from the returned array. You should probably include them, or at least document that they are omitted.

If the number is negative, you return null. While in theory negative numbers have divisors (and positive numbers have negative divisors), I understand why this you chose this approach, as well as why you only return positive divisors. I would suggest you either document this behavior, or enforce it by using the uint datatype. I would chose the former approach, as intis much more prevalent, and using uint would most likely imply a lot of casting down the line.

Optimizing the algorithm

You check if the number is prime before looking for divisors. First of all, your algorithm for primality checking is rather naive and can be optimized in various ways. More importantly, this is an optimization only if the argument is prime, but is counterproductive in the vast majority of cases when it isn't prime. I suggest to simply get rid of that check.

Furthermore, you check if every number between 2 and n is a divisor of n; however, you know that if i is a divisor, so is n / i. Therefore, you can loop only on values between 1 and sqrt(n) and add two divisors for every match.

My attempt

    public static class Divisors
    {
        /// <summary>
        /// Finds all the divisors of any positive integer passed as argument. 
        /// Returns an array of int with all the divisors of the argument.
        /// Returns null if the argument is zero or negative.
        /// </summary>
        public static int[] GetDivisorsMe(int n)
        {
            if (n <= 0)
            {
                return null;
            }
            List<int> divisors = new List<int>();
            for (int i = 1; i <= Math.Sqrt(n); i++)
            {
                if (n % i == 0)
                {
                    divisors.Add(i);
                    if (i != n / i)
                    {
                        divisors.Add(n / i);
                    }
                }
            }
            divisors.Sort();
            return divisors.ToArray();
        }
    }

As for performance, finding all divisors for every integer between 0 and 10,000 takes around 130ms with your solution on my machine vs 12ms with mine, so a performance gain of around 10x.
Finding divisors for int.MaxValue takes around 9s your solution vs 5ms with mine, a performance gain greater than 1000x!
Finally, finding divisors for 2095133040 – the largest highly composite number that fits in the int datatype, with a total of 1600 divisors – takes around 5s with your solution, vs 13ms with my solution, again a performance gain of around 400x.

Performance can probably be improved further by estimating how many divisors has a given input and passing that estimate to the List<int> constructor, and thus limiting how much memory reallocating is done as the list grows. In fact, the upper bound of the number divisors is known: 1600. You could simply allocate the list as:

List<int> divisors = new List<int>(1600);

This brings the execution time down to 5ms for the highest composite number, but feels like a waste of memory in most cases.

Answer 2

I saw it would be better if I post an answer instead of using comments.

For your IsPrime method, I see that you've covered most conditions, but you forgot to cover 0, 1, and -n cases, which you can just do with a small change on this line :

if (n % 2 == 0) return false;

to

if (n < 2 || n % 2 == 0) return false;

suggested :

public static bool IsPrime(int n)
{
    if(n == 2) { return true; }

    if (n < 2 || (n % 2 == 0)) { return false; }

    for (int x = 3; x * x <= n; x += 2)
    {
        if (n % x == 0) { return false; }
    }

    return true;
}

For GetDivisors. I assume that you excluded 1 and n from the results, since it's already known that every natural number is divisible by 1 and itself, which is fine if you intended to use this code personally, but it is uncommon to do that, and it might even conflict with other developers code, as you don't want to assume everybody knows that! so it must be included to make the code more usable for others, and you must always consider what is common use, and what is not.

The technique in @gazoh answer is a really good one, and I would take it to the next level, but I have to note out that Sort and ToArray are expensive operations as I've mentioned in the comments. And I would avoid using them directly.

I've updated this method to :

private static IEnumerable<int> GetDivisors(int n)
{
    if (n <= 0) { yield return default; }

    int iterator = (int)Math.Sqrt(n);

    for (int i = 1; i <= iterator; i++)
    {
        if (n % i == 0)
        {
            yield return i;                    

            if (i != n / i) { yield return n / i; }
        }
    }
}

public static IEnumerable<int> GetDivisors(int n, bool AscendingOrder = false)
{
    return !AscendingOrder ? GetDivisors(n) : GetDivisors(n).OrderBy(x => x);
}

I've used IEnumerable<int> to open more acceptable collections types rather than just sticking with an array. The overload is just to have an option to order the data, while the default is unordered data. This would make it optional, which would depend on usage, if you prefer performance over order, or order over performance. Then you can convert it to list or array or any collection.

For performance differences, I've used BenchmarkDotNet to test and compare this method performance and here is the results.

Test 1 using GetDivisors(2095133040)

|             Method |                 Mean |               Error |              StdDev |
|------------------- |---------------------:|--------------------:|--------------------:|
|           Original | 5,907,229,864.000 ns | 116,153,274.6298 ns | 155,061,285.3568 ns |
|            ByGazoh |       169,411.783 ns |       2,805.6563 ns |       2,487.1413 ns |
|   IEnumerable<int> |             6.637 ns |           0.1896 ns |           0.2107 ns |
|            OrderBy |            17.514 ns |           0.3013 ns |           0.2516 ns |
|            ToArray |       151,408.141 ns |       2,906.1875 ns |       2,854.2648 ns |
|             ToList |       363,424.079 ns |       5,318.8335 ns |       4,975.2401 ns |
|  ToArray + OrderBy |       154,249.309 ns |       2,370.8673 ns |       2,101.7121 ns |
|   ToList + OrderBy |       356,705.127 ns |       6,002.7773 ns |       5,321.3057 ns |

Test 2 using GetDivisors(1600)

|             Method |         Mean |      Error |     StdDev |
|------------------- |-------------:|-----------:|-----------:|
|           Original | 4,804.474 ns | 93.0708 ns | 91.4080 ns |     
|           ByGazoh  |   515.822 ns |  7.6545 ns |  7.1601 ns |     
|   IEnumerable<int> |     6.391 ns |  0.0966 ns |  0.0904 ns |     
|            OrderBy |    16.783 ns |  0.2839 ns |  0.2517 ns |     
|            ToArray |   422.570 ns |  6.3368 ns |  5.9274 ns |     
|             ToList |   463.575 ns |  8.0975 ns |  7.5744 ns |
|  ToArray + OrderBy | 1,662.728 ns | 26.8204 ns | 25.0878 ns |
|   ToList + OrderBy | 1,634.595 ns | 30.9492 ns | 28.9499 ns |

ns = nano-second;

Where

• OrderBy = Divisors.GetDivisors(n).OrderBy(x=>x);
• ToArray = Divisors.GetDivisors(n).ToArray();
• ToList = Divisors.GetDivisors(n).ToList();
• ToArray + OrderBy = Divisors.GetDivisors(n).OrderBy(x=>x).ToArray();
• ToList + OrderBy =Divisors.GetDivisors(n).OrderBy(x=>x).ToList();

Lastly, regarding your tests, I suggest you test each scenario separately.

Example :

[TestMethod]
public void GetDivisors_15_IsEqual()
{
    Assert.AreEqual(new int[] { 3, 5 }, Divisors.Divisors(15));
}

[TestMethod]
public void GetDivisors_16_IsEqual()
{
    Assert.AreEqual(new int[] { 2, 4, 8 }, Divisors.Divisors(16));
}

[TestMethod]
public void GetDivisors_253_IsEqual()
{
    Assert.AreEqual(new int[] { 11, 23 }, Divisors.Divisors(253));
}

[TestMethod]
public void GetDivisors_24_IsEqual()
{
    Assert.AreEqual(new int[] { 2, 3, 4, 6, 8, 12 }, Divisors.Divisors(24));
}

 the reason is simple, if you create a separate test for each scenario you have, it'll be easy to determine which part of your code needs adjustments, and it would make things easier for improving your code (say you want to simplify it without breaking the code). Also, it would be more easier to read and follow, and could give you a better view on the requirements, and the validation process of it.

If you don't detailed your tests, in smaller projects you might not have any issues, but in big projects, it'll be a pain in the neck.

I hope this would be useful.

Answer 3

You can get a vast improvement in speed: If x is divisible by y, then x is also divisible by (x / y) with the result y.

So if you try to get the divisors of 1,000,000,000,000 you only need to divide by the numbers 1 to 1,000,000 and add two divisors to your list at a time instead of 1. The exception is when x is a square and x/y = y since you don’t want to add the same divisor twice.

Answer 4

What I need is to optimize this code to be as fast as possible.

That's premature. Start by making the code correct. For example, you do a multiplication of x*x in your primality check, but that can overflow.

Once you have the code correct, then run the code through a profiler to find out where the slow parts are and attack those one at a time.

What you will discover is that you are spending a huge amount of time checking to see if numbers are primes.

Let's think about this a bit. You want the divisors of a positive 32 bit integer, so it is between 1 and around two billion. If the number is composite then its largest prime factor will be less than 45000. But there are only about 5000 primes less than 45000. Calculate them all once and put them in a sorted list. You can then binary search that list very quickly, or build a more optimized lookup.

The algorithm now becomes:

• If the number is less than 45000, just check to see if it is on the list; that's binary-searchable.
• If the number is greater than 45000, check to see if it is divisible by any prime. That does a maximum of about 5000 checks and you don't waste any time checking non-primes.

Now let's think about it harder.

What is your algorithm for finding divisors?

• Do an expensive test to see if a number is prime; if it is, it only has two divisors.
• Otherwise, check every possible divisor up to its square root.

This algorithm is incredibly expensive. We've seen that we can make the first part cheaper. Can we make the second part cheaper?

Yes. A far better algorithm is:

• Determine the prime factorization of the number
• The divisors are all possible products of prime factors

The trick here is that for composite numbers, determining prime factors can be sped up.

Let's see how. Suppose you want the prime factors of 36.

We start by noting that 36 is divisible by 2. Now comes the trick. The prime factors of 36 are 2, followed by the prime factors of 18. We just made the problem smaller.

18 is divisible by 2 as well, so the prime factors of 36 are 2, 2, and the prime factors of 9. Again, we've made the problem smaller.

What are the prime factors of 9? 2 doesn't work, so we bump up to 3. 3 works. So the prime factors of 36 are 2, 2, 3 and the prime factors of 3.

What are the prime factors of 3? We do not start again at 2, because we know that we've already taken out all possible 2s. We start at 3, and get down to 1, and we're done. The prime factors of 36 are 2, 2, 3, 3.

That solves the first problem. The second problem is then generate all possible products. The way to do this is to generate all possible combinations of 0, 1 and 2 as follows:

0 0 is 1 * 1 = 1
0 1 is 1 * 3 = 3
0 2 is 1 * 3 * 3 = 9
1 0 is 2 * 1 = 2
1 1 is 2 * 3 = 6
1 2 is 2 * 3 * 3 = 18

and so on. Generate all possible combinations of products, put their results in an array, and sort that ascending.

This algorithm is more complicated but it is typically much faster when the numbers get big.