{"id":587,"date":"2012-08-07T01:53:35","date_gmt":"2012-08-07T05:53:35","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=587"},"modified":"2012-09-07T16:09:38","modified_gmt":"2012-09-07T20:09:38","slug":"project-euler-problem-46","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/07\/project-euler-problem-46\/","title":{"rendered":"Project Euler &#8211; Problem 46"},"content":{"rendered":"<p>Problem 46: What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.util.Vector;\r\n\r\n\r\nclass runner\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\t\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\r\n\t\tprimes.add(2);\r\n\t\tint n = 3;\r\n\t\touterLoop:\r\n\t\twhile(true){\r\n\t\t\tif(!isPrime(n) && n % 2 == 1){\r\n\t\t\t\tboolean found = false;\r\n\t\t\t\tfor(int p: primes){\r\n\t\t\t\t\tif(p < n-1){\r\n\t\t\t\t\t\tdouble sqrtdiff = Math.sqrt((n-p)\/2.0);\r\n\t\t\t\t\t\tif(Math.floor(sqrtdiff) == sqrtdiff){\r\n\t\t\t\t\t\t\tfound = true;\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t\t\r\n\t\t\t\tif(!found){\r\n\t\t\t\t\tbreak outerLoop;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\tn++;\r\n\t\t}\r\n\t\t\r\n\t\tSystem.out.println(\"n: \"+n);\r\n\t\t\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 46: What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?<\/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-587","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/587","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=587"}],"version-history":[{"count":2,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/587\/revisions"}],"predecessor-version":[{"id":755,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/587\/revisions\/755"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}