{"id":532,"date":"2014-01-01T19:25:07","date_gmt":"2014-01-01T23:25:07","guid":{"rendered":"http:\/\/www.peteonsoftware.com\/?p=532"},"modified":"2014-01-01T19:25:07","modified_gmt":"2014-01-01T23:25:07","slug":"prime-factorizations","status":"publish","type":"post","link":"https:\/\/www.peteonsoftware.com\/index.php\/2014\/01\/01\/prime-factorizations\/","title":{"rendered":"Prime Factorizations"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/www.peteonsoftware.com\/images\/201401\/PrimeFactorization.png\" alt=\"Prime Factorization\" title=\"Prime Factorization\" style=\"float: left; margin: .5em;\" \/>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:<br \/>\n<br style=\"clear:both;\" \/><\/p>\n<p><script src=\"https:\/\/gist.github.com\/PeteShearer\/8149301.js\"><\/script><\/p>\n<p>You call it like so: <\/p>\n<pre>\r\nvar primeFactors = PrimeFactors.Of(1305294);\r\n<\/pre>\n<p>I&#8217;ve run tests on this and some timings.  Here are some representative findings:<\/p>\n<pre>\r\n   198,602 = 2 * 199 * 499 (40 milliseconds to run)\r\n 4,678,421 = 11 * 101 * 4,211 (3,131 milliseconds to run)\r\n17,841,257 = 7 * 2,548,751 (20,603 milliseconds to run) \r\n<\/pre>\n<p>2,548,751 is a pretty big prime! (Verified by <a href=\"http:\/\/is.2548751.aprimenumber.com\/\">http:\/\/is.2548751.aprimenumber.com\/<\/a>.)<\/p>\n<p>I use the trick that says that a number is prime if it isn&#8217;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&#8217;t know if there is a better or more elegant way to attack that.<\/p>\n<p>I&#8217;d be interested in any feedback and in seeing how some other people might solve the problem.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[20],"tags":[91],"class_list":["post-532","post","type-post","status-publish","format-standard","hentry","category-fluff","tag-fluff"],"_links":{"self":[{"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/posts\/532","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/comments?post=532"}],"version-history":[{"count":0,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/posts\/532\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/media?parent=532"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/categories?post=532"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/tags?post=532"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}