Skip to content

Finding Factors

October 27, 2008

nemo

So I recently had a need to find all the factors of an integer.  ie. All the numbers that evenly divide into a number.  eg. "4 = 4, 1, 2" Like most things I was keen to find the most elegant and efficient way to go about it.  I played around with the problem a bit and eventually took my case to the good people over at StackOverflow.  This is the result of playing with some of the ideas that people threw out there.

static IEnumerable<int> GetFactors2(int x)
        {
            return from a in Enumerable.Range(1, x)
                          where x % 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;
                }
            }
        }

I took a little extra time to do some performance testing.  The results were as I expected.

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

Note that the LINQ one that examines all the possible numbers doesn’t scale well at all.  This isn’t a LINQ thing just how it was implemented, it might even be worse in a for loop.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: