C# Code to Find all Divisors of an Integer 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 &lt;= n; x += 2)
            if (n % x == 0)
                return false;

        return true;
    }

    public static int[] GetDivisors(int n)
    {
        List&lt;int&gt; divisors = new List&lt;int&gt;();

        if (n &lt; 2)
        {
            return null;
        }
        else if (IsPrime(n))
        {
            return null;
        }
        else
        {
            for (int i = 2; i &lt; 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));
    }
  }
}
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
    {
        /// &lt;summary&gt;
        /// 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.
        /// &lt;/summary&gt;
        public static int[] GetDivisorsMe(int n)
        {
            if (n &lt;= 0)
            {
                return null;
            }
            List&lt;int&gt; divisors = new List&lt;int&gt;();
            for (int i = 1; i &lt;= 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 &ndash; the largest highly composite number that fits in the int datatype, with a total of 1600 divisors &ndash; 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&lt;int&gt; 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&lt;int&gt; divisors = new List&lt;int&gt;(1600);


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