Best way to find all factors of a given number

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-5,445,881
• GetFactors2-4,308,234
• GetFactors3-2,913,659

When factoring the number 20000, 5 times each:

• GetFactors1-5,644,457
• GetFactors2-12,117,938
• GetFactors3-3,108,182

Solution 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) 
{
    var 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 != number/factor) // 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.

Solution 2

The % (remainder) operator is the one to use here. 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.

Solution 3

Very late but the accepted answer (a while back) didn't not give the correct results.

Thanks to Merlyn, I got now got the reason for the square as a 'max' below the corrected sample. althought the answer from Echostorm seems more complete.

public static IEnumerable<uint> GetFactors(uint x)
{
    for (uint i = 1; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            yield return i;
            if (i != x / i)
                yield return x / i;
        }
    }
}

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

Solution 5

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


        }

View more solutions