Alex Rivera | Logout

Best way to find all factors of a given number

Asked 2008-10-27T13:28:52.440
38

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
Edit
Report

1 Answer

14

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;
        }
    }
}
answered 2010-08-08T05:41:35.747

Your Answer