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

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

From stackoverflow Echostorm

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.

Jon Skeet : One extra check to add - the above will add 2 twice :)

Echostorm : Math.Sqrt returns a double. Also, that needs to be rounded up. Try using 20 as an example.

Mark Ransom : Rather than taking the square root, you can restructure the loop: for(int factor = 1; factor*factor <= number; ++factor)

Chris Marasti-Georg : True - and I would imagine there is a point past which performance would degrade for that, since you are calculating it on each loop? It is probably not as significant as other parts of the loop. Benchmarking would have to be performed, I suppose.

Echostorm : cool idea Mark. you have to test against factor * factor != x when you're yielding tho.

From Chris Marasti-Georg
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#.

From Jon Skeet
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;
}
```
Chris Marasti-Georg : This is wrong - it only returns half of them.

Jay Bazuzi : This only gets you the first 1/2 of factors. e.g., for 10, it would return 1 and 2, but not 5 and 10.

Jon Skeet : Suggested change: Math.Sqrt will return a double, which won't work with Enumerable.Range. Also that won't return 4 - just 1 and 2.

From Marcel Popescu

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.

From Jay Bazuzi

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).

From $pageUsers[$post.author].name

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.

Chris Marasti-Georg : Why not just edit the old answer?

Jay Bazuzi : Because they are two different answers, with differing merit.

From Jay Bazuzi

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

From mspmsp

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;
            }


        }

From pablito

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;
            }
        }
    }
```
From call me Steve

Code Answer

Sunday, February 13, 2011

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

0 comments:

Post a Comment

Blog Archive