Fluff

Prime Factorizations

Prime FactorizationI 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.

Leave a Reply

Your email address will not be published. Required fields are marked *