{"id":589,"date":"2012-08-07T02:24:42","date_gmt":"2012-08-07T06:24:42","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=589"},"modified":"2012-09-07T16:09:33","modified_gmt":"2012-09-07T20:09:33","slug":"project-euler-problem-47","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/07\/project-euler-problem-47\/","title":{"rendered":"Project Euler &#8211; Problem 47"},"content":{"rendered":"<p>Problem 47: Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?<br \/>\n<!--more--><br \/>\nThe first two consecutive numbers to have two distinct prime factors are:<br \/>\n<center><\/p>\n<pre>14 = 2 x 7\r\n15 = 3  5<\/pre>\n<p><\/center><\/p>\n<p>The first three consecutive numbers to have three distinct prime factors are:<br \/>\n<center><\/p>\n<pre>644 = 2^2 x 7 x 23\r\n645 = 3 x 5 x 43\r\n646 = 2 x 17 x 19.<\/pre>\n<p><\/center><\/p>\n<p><code><\/p>\n<pre lang='java'>\r\nimport java.util.Vector;\r\n\r\n\r\nclass runner\r\n{\r\n\tpublic static int numOfDistinctFactors(int n){\r\n\t\tdouble limit = n\/2;\r\n\t\tint c = 0;\r\n\r\n\t\tint pp = primes.lastElement();\r\n\t\twhile(primes.lastElement() < limit){\r\n\t\t\tisPrime(++pp);\/\/Check and store primes until limit\r\n\t\t}\r\n\r\n\t\tfor(int p : primes){\r\n\t\t\tif(p > limit || n == 1) break;\r\n\t\t\tif(n % p == 0){\r\n\t\t\t\tdo{\r\n\t\t\t\t\tn \/= p;\r\n\t\t\t\t}while(n % p == 0);\r\n\t\t\t\tc++;\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\treturn c;\r\n\t}\r\n\r\n\tpublic static boolean isPrime(int n){\r\n\t\tif(primes.contains(n)) return true;\r\n\t\tdouble limit = Math.sqrt(n);\r\n\t\tfor(int p: primes){\r\n\t\t\tif(p > limit) break;\r\n\t\t\tif(n % p == 0) return false;\r\n\t\t}\r\n\t\tprimes.add(n);\r\n\t\treturn true;\r\n\t}\r\n\r\n\tstatic Vector<Integer> primes = new Vector<Integer>();\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\t\tprimes.add(2);\r\n\r\n\t\tint i=644;\r\n\t\tint consec_reset = 4, consec = consec_reset;\r\n\t\twhile(true){\r\n\t\t\tif(numOfDistinctFactors(i) == consec_reset){\r\n\t\t\t\tconsec -= 1;\r\n\t\t\t}else{\r\n\t\t\t\tconsec = consec_reset;\r\n\t\t\t}\r\n\r\n\t\t\tif(consec == 0) break;\r\n\t\t\ti++;\r\n\t\t}\r\n\t\ti-=consec_reset-1;\r\n\t\t\r\n\t\tSystem.out.println(\"i:\"+i);\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\nNote: Execution time is about 9.7seconds<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 47: Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[56],"tags":[],"class_list":["post-589","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/589","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/comments?post=589"}],"version-history":[{"count":5,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/589\/revisions"}],"predecessor-version":[{"id":754,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/589\/revisions\/754"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=589"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=589"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=589"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}