I was checking out the internet and I came across someone doing a code kata for prime factorizations. I stopped watching what they were doing and decided to try my own hand at it. Here is the result:
You call it like so:
var primeFactors = PrimeFactors.Of(1305294);
I’ve run tests on this and some timings. Here are some representative findings:
198,602 = 2 * 199 * 499 (40 milliseconds to run) 4,678,421 = 11 * 101 * 4,211 (3,131 milliseconds to run) 17,841,257 = 7 * 2,548,751 (20,603 milliseconds to run)
2,548,751 is a pretty big prime! (Verified by http://is.2548751.aprimenumber.com/.)
I use the trick that says that a number is prime if it isn’t divisible by any of the numbers up to its square root. That definitely sped up performance. Other than that, I think the biggest spot for potential refactoring is around actually checking and calculating the prime factors. I laid it out very much like I would do the prime factorization with pencil and paper, but I don’t know if there is a better or more elegant way to attack that.
I’d be interested in any feedback and in seeing how some other people might solve the problem.
