Best way to find all factors of a given number in C#

Question

All numbers that divide evenly into x.

I put in 4 it returns: 4, 2, 1

edit: I know it sounds homeworky. I'm writing a little app to populate some product tables with semi random test data. Two of the properties are ItemMaximum and Item Multiplier. I need to make sure that the multiplier does not create an illogical situation where buying 1 more item would put the order over the maximum allowed. Thus the factors will give a list of valid values for my test data.

edit++: This is what I went with after all the help from everyone. Thanks again!

edit#: I wrote 3 different versions to see which I liked better and tested them against factoring small numbers and very large numbers. I'll paste the results.

static IEnumerable<int> GetFactors2(int n)
        {
            return from a in Enumerable.Range(1, n)
                          where n % a == 0
                          select a;                      
        }

        private IEnumerable<int> GetFactors3(int x)
        {            
            for (int factor = 1; factor * factor <= x; factor++)
            {
                if (x % factor == 0)
                {
                    yield return factor;
                    if (factor * factor != x)
                        yield return x / factor;
                }
            }
        }

        private IEnumerable<int> GetFactors1(int x)
        {
            int max = (int)Math.Ceiling(Math.Sqrt(x));
            for (int factor = 1; factor < max; factor++)
            {
                if(x % factor == 0)
                {
                    yield return factor;
                    if(factor != max)
                        yield return x / factor;
                }
            }
        }

In ticks. When factoring the number 20, 5 times each:

• GetFactors1-5445881
• GetFactors2-4308234
• GetFactors3-2913659

When factoring the number 20000, 5 times each:

• GetFactors1-5644457
• GetFactors2-12117938
• GetFactors3-3108182

Answer 1

pseudocode:

• Loop from 1 to the square root of the number, call the index "i".
• if number mod i is 0, add i and number / i to the list of factors.

realocode:

public List<int> Factor(int number) {
    List<int> factors = new List<int>();
    int max = (int)Math.Sqrt(number);  //round down
    for(int factor = 1; factor <= max; ++factor) { //test from 1 to the square root, or the int below it, inclusive.
        if(number % factor == 0) {
            factors.add(factor);
            if(factor != max) { // Don't add the square root twice!  Thanks Jon
                factors.add(number/factor);
            }
        }
    }
    return factors;
}

As Jon Skeet mentioned, you could implement this as an IEnumerable<int> as well - use yield instead of adding to a list. The advantage with List<int> is that it could be sorted before return if required. Then again, you could get a sorted enumerator with a hybrid approach, yielding the first factor and storing the second one in each iteration of the loop, then yielding each value that was stored in reverse order.

You will also want to do something to handle the case where a negative number passed into the function.

Answer 2

Is this homework? If so, I'd rather walk you through you solving it than just give you an answer.

Are you aware of the % (remainder) operator? If x % y == 0 then x is divisible by y. (Assuming 0 < y <= x)

I'd personally implement this as a method returning an IEnumerable<int> using an iterator block, but that's relatively advanced if you're fairly new to C#.

Answer 3

Linq solution:

IEnumerable<int> GetFactors(int n)
{
  Debug.Assert(n >= 1);
  return from i in Enumerable.Range(1, n)
         where n % i == 0
         select i;
}

Answer 4

As extension methods:

    public static bool Divides(this int potentialFactor, int i)
    {
        return i % potentialFactor == 0;
    }

    public static IEnumerable<int> Factors(this int i)
    {
        return from potentialFactor in Enumerable.Range(1, i)
               where potentialFactor.Divides(i)
               select potentialFactor;
    }

Here's an example of usage:

        foreach (int i in 4.Factors())
        {
            Console.WriteLine(i);
        }

Note that I have optimized for clarity, not for performance. For large values of i this algorithm can take a long time.

Answer 5

How big is x going to be?

For small numbers, you can get away with a naive solution, but for larger x it would be useful to implement a better algorithm (Wikipedia describes some).

Answer 6

Here it is again, only counting to the square root, as others mentioned. I suppose that people are attracted to that idea if you're hoping to improve performance. I'd rather write elegant code first, and optimize for performance later, after testing my software.

Still, for reference, here it is:

    public static bool Divides(this int potentialFactor, int i)
    {
        return i % potentialFactor == 0;
    }

    public static IEnumerable<int> Factors(this int i)
    {
        foreach (int result in from potentialFactor in Enumerable.Range(1, (int)Math.Sqrt(i))
                               where potentialFactor.Divides(i)
                               select potentialFactor)
        {
            yield return result;
            if (i / result != result)
            {
                yield return i / result;
            }
        }
    }

Not only is the result considerably less readable, but the factors come out of order this way, too.

Answer 7

Wouldn't it also make sense to start at 2 and head towards an upper limit value that's continuously being recalculated based on the number you've just checked? See N/i (where N is the Number you're trying to find the factor of and i is the current number to check...) Ideally, instead of mod, you would use a divide function that returns N/i as well as any remainder it might have. That way you're performing one divide operation to recreate your upper bound as well as the remainder you'll check for even division.

Math.DivRem http://msdn.microsoft.com/en-us/library/wwc1t3y1.aspx

Answer 8

Another LINQ style and tying to keep the O(sqrt(n)) complexity

        static IEnumerable<int> GetFactors(int n)
        {
            Debug.Assert(n >= 1);
            var pairList = from i in Enumerable.Range(1, (int)(Math.Round(Math.Sqrt(n) + 1)))
                    where n % i == 0
                    select new { A = i, B = n / i };

            foreach(var pair in pairList)
            {
                yield return pair.A;
                yield return pair.B;
            }


        }

Answer 9

A bit late but the accepted answer does not give the correct results. (at least the 3 different answers does not give the results even if they run in similar time)

I don't know why there is a limit set at the square root ? It's been a while since I did some math but it seems that we can only divide by two (maybe 3 for odd number to decrease a little bit the runtime?)

    public static IEnumerable<uint> getFactors(uint x)
    {
        uint max = x / 2;
        for (uint i = 1; i <= max; i++)
        {
            if (0 == (x % i))
            {
                yield return i;
            }
        }
    }