Getting Factors of a Number

Question

I'm trying to refactor this algorithm to make it faster. What would be the first refactoring here for speed?

public int GetHowManyFactors(int numberToCheck)
    {
        // we know 1 is a factor and the numberToCheck
        int factorCount = 2; 
        // start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor
        for (int i = 2; i < numberToCheck; i++) 
        {
            if (numberToCheck % i == 0)
                factorCount++;
        }
        return factorCount;
    }

Answer 1

The first optimization you could make is that you only need to check up to the square root of the number. This is because factors come in pairs where one is less than the square root and the other is greater.

One exception to this is if n is an exact square then its square root is a factor of n but not part of a pair.

For example if your number is 30 the factors are in these pairs:

• 1 x 30
• 2 x 15
• 3 x 10
• 5 x 6

So you don't need to check any numbers higher than 5 because all the other factors can already be deduced to exist once you find the corresponding small factor in the pair.

Here is one way to do it in C#:

public int GetFactorCount(int numberToCheck)
{
    int factorCount = 0;
    int sqrt = (int)Math.Ceiling(Math.Sqrt(numberToCheck));

    // Start from 1 as we want our method to also work when numberToCheck is 0 or 1.
    for (int i = 1; i < sqrt; i++)
    {
        if (numberToCheck % i == 0)
        {
            factorCount += 2; //  We found a pair of factors.
        }
    }

    // Check if our number is an exact square.
    if (sqrt * sqrt == numberToCheck)
    {
        factorCount++;
    }

    return factorCount;
}

There are other approaches you could use that are faster but you might find that this is already fast enough for your needs, especially if you only need it to work with 32-bit integers.