# Finding Factors

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.