{"id":599,"date":"2012-08-07T22:52:31","date_gmt":"2012-08-08T02:52:31","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=599"},"modified":"2012-09-07T16:08:55","modified_gmt":"2012-09-07T20:08:55","slug":"project-euler-problem-50","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/07\/project-euler-problem-50\/","title":{"rendered":"Project Euler &#8211; Problem 50"},"content":{"rendered":"<p>Problem 50: Which prime, below one-million, can be written as the sum of the most consecutive primes?<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nclass runner\r\n{\r\n\t\/\/true means composite\r\n\tpublic static int sieveArray(boolean[] arr){\r\n\t\tint numOfPrimes = 0;\r\n\t\tarr[0] = true; arr[1] = true;\r\n\t\tfor(int i=2;i<arr.length\/2; i++){\r\n\t\t\tif(arr[i]) continue;\r\n\t\t\tint next = i+i;\r\n\t\t\twhile(next < arr.length){\r\n\t\t\t\tarr[next] = true;\r\n\t\t\t\tnumOfPrimes++;\r\n\t\t\t\tnext += i;\r\n\t\t\t}\r\n\t\t}\r\n\t\treturn numOfPrimes;\r\n\t}\r\n\r\n\tprivate static int[] convertArr(int num, boolean[] arr2){\r\n\t\tint[] arr = new int[num];\r\n\t\tint k = 0;\r\n\t\tfor(int i=0;i<arr2.length;i++){\r\n\t\t\tif(!arr2[i]) arr[k++] = i; \r\n\t\t}\r\n\t\treturn arr;\r\n\t}\r\n\t\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\tint l=0,lp=5;\r\n\t\t\r\n\t\tboolean[] arr = new boolean[1000000];\r\n\t\tint numOfPrimes = sieveArray(arr);\r\n\t\t\r\n\t\tint[] primes = convertArr(numOfPrimes, arr);\/\/drops size from 1mil to around 78-79k\r\n\t\t\r\n\t\tint primesum = 0;\r\n\t\tint primeIdx = -1;\r\n\t\tfor(int n=1; n<primes.length; n++){\r\n\t\t\tint nval = primes[n];\r\n\r\n\t\t\twhile(primesum+primes[1+primeIdx] <= nval){\r\n\t\t\t\tprimesum += primes[++primeIdx];\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\tint curIdx = primeIdx;\r\n\t\t\tint cursum = primesum;\r\n\t\t\tfor(int i=0; i<n; i++){\r\n\t\t\t\tint ival = primes[i];\r\n\t\t\t\tif(cursum == nval){\r\n\t\t\t\t\tif(l<(curIdx-i)){\r\n\t\t\t\t\t\tl = (curIdx-i);\r\n\t\t\t\t\t\tlp = nval;\r\n\t\t\t\t\t}\r\n\t\t\t\t\t\/\/System.out.println(\"p:\"+nval+\" len:\"+(curIdx-i)+\" start:\"+ival);\r\n\t\t\t\t\tbreak;\r\n\t\t\t\t}\r\n\t\t\t\tcursum-=ival;\r\n\t\t\t\twhile(cursum < nval &#038;&#038; curIdx+1 < n){\r\n\t\t\t\t\tcursum += primes[++curIdx];\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\tSystem.out.println(\"lp:\"+lp+\" l:\"+l);\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><br \/>\nNote: If using Vectors for the array \"primes\", the execution time will increase from 34s to 2.8minutes.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 50: Which prime, below one-million, can be written as the sum of the most consecutive primes?<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[56],"tags":[],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/599"}],"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=599"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/599\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=599"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=599"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=599"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}