{"id":1183,"date":"2015-06-17T12:27:44","date_gmt":"2015-06-17T19:27:44","guid":{"rendered":"http:\/\/www.coastalvectors.com\/blog\/?p=1183"},"modified":"2017-09-07T14:13:54","modified_gmt":"2017-09-07T21:13:54","slug":"project-euler-357","status":"publish","type":"post","link":"https:\/\/www.coastalvectors.com\/blog\/2015\/06\/project-euler-357\/","title":{"rendered":"Project Euler 357"},"content":{"rendered":"<p><a href=\"http:\/\/www.coastalvectors.com\/blog\/wp-content\/uploads\/2015\/06\/check.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-1184\" src=\"http:\/\/www.coastalvectors.com\/blog\/wp-content\/uploads\/2015\/06\/check.jpg\" alt=\"check\" width=\"150\" height=\"150\" \/><\/a>I recently completed <a href=\"https:\/\/projecteuler.net\/problem=357\">Project Euler 357<\/a> after working on it here and there over the course of a couple of days. I decided to do this one out of order because it seemed like a fairly straight foward problem.<\/p>\n<blockquote>\n<div class=\"problem_content\">\n<p>Consider the divisors of 30: 1,2,3,5,6,10,15,30.<br \/>\nIt can be seen that for every divisor <var>d<\/var> of 30, <var>d<\/var>+30\/<var>d<\/var> is prime.<\/p>\n<p>Find the sum of all positive integers <var>n<\/var> not exceeding 100 000 000<br \/>\nsuch that for every divisor <var>d<\/var> of <var>n<\/var>, <var>d<\/var>+<var>n<\/var>\/<var>d<\/var> is prime.<\/p>\n<\/div>\n<\/blockquote>\n<div class=\"problem_content\">\n<p>This shouldn&#8217;t be hard. Just find the divisors of every number, and see if n+1 is prime. Heck, I already have an isPrime() function written! The brute force approach will be easy to code.<\/p>\n<p>I started off with code resembing this:<\/p>\n<pre><code>bool isPrimeGen(int n, bool *primes)\r\n{\r\n    for (int d=1; d&lt;=n; d++)\r\n        if (n % d == 0)\r\n            if (primes[d+n\/d] != true)\r\n                return false;\r\n    return true;\r\n}\r\nint main()\r\n{\r\n    int limit = 100000000;\r\n    unsigned long long sum = 1;\r\n    for (int i=2; i&lt;limit; i++)\r\n        if (isPrimeGen(i))\r\n            sum += i;\r\n    printf(\"%d\", sum)\r\n}<\/code><\/pre>\n<p>Well, this worked&#8230; But it took far too long. It took over 4 hours to complete. Obviously this doesn&#8217;t fit in with the guidlines that solutions should take less than a minute to complete.<\/p>\n<p>I was able to make a single optimization that got the time down from 4 hours to 12 minutes. A single, tiny change. (It&#8217;s actually a similar optimization I made to my prime function when I first started doing these Euler problems&#8230;) Instead of looking for every divisor up to the size of n, our number, I put in a square root n, sqrt(n), as the limit for divisor checking.<\/p>\n<p>Another optimization was to make use of looking for patterns in the qualifying numbers.<\/p>\n<ul>\n<li>n is always even<\/li>\n<li>n is always 1 less than a prime number<\/li>\n<li>n\/2+2 is always a prime number<\/li>\n<\/ul>\n<p>Filtering down the potential numbers by using these patterns further reduced the time, but it was still taking longer than I would have liked. I decided to take drastic measures&#8230; I pre-computed a ton of primes using a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Sieve_of_Eratosthenes\">Seive of Eratosthenes<\/a>.<\/p>\n<p>I made a giant boolean array where any number is marked as a prime or not. This made looking up whether or not primes are numbers super trivial. I&#8217;m not sure this is the most elegant solution, but it seemed simple and fast.<\/p>\n<pre><code>\/\/ Generate primes using sieve\r\nbool *primes = malloc(limit*sizeof(bool));\r\nfor (int i=2; i&lt;limit; i++)\r\n    primes[i] = true;\r\nprimes[0] = false;\r\nprimes[1] = false;\r\nfor (int i=2; i&lt;limit; i++)\r\n    if (primes[i] == true)\r\n    {\r\n        int n = 2;\r\n        while (n*i &lt; limit)\r\n            primes[i*n++] = false;\r\n    }<\/code><\/pre>\n<p>So, this generates an array, and I pre-load the value for each number as &#8216;true&#8217; (excepting for 0 and 1 of course). I then go through sequentially, and if I hit a number that is &#8216;true,&#8217; or prime, every multiple of that number gets marked as &#8216;false,&#8217; or not prime, until we reach the limit of the array. This is a super fast method for calculating an obscene number of primes very quickly because it doesn&#8217;t require any division.<\/p>\n<p>With this pre-loaded table of primes, the code was then refactored to make use of this table rather than my standard isPrime() function.<\/p>\n<p>Putting all these changes together allowed the problem to be solved in under 5 seconds, which is just a tad better than my original 4 hours.<\/p>\n<p>Of course, I won&#8217;t reveal the answer here. You&#8217;ll need to figure that out on your own. You can, however, check out my <a href=\"https:\/\/github.com\/mryingster\/ProjectEuler\/blob\/master\/problem_357.c\">full solution<\/a> on my <a href=\"https:\/\/github.com\/mryingster\/\">GitHub account<\/a>.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>I recently completed Project Euler 357 after working on it here and there over the course of a couple of days. I decided to do this one out of order because it seemed like a fairly straight foward problem. Consider the divisors of 30: 1,2,3,5,6,10,15,30. It can be seen that for every divisor d of &hellip; <a href=\"https:\/\/www.coastalvectors.com\/blog\/2015\/06\/project-euler-357\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Project Euler 357<\/span><\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-1183","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1183","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/comments?post=1183"}],"version-history":[{"count":4,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1183\/revisions"}],"predecessor-version":[{"id":1189,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1183\/revisions\/1189"}],"wp:attachment":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/media?parent=1183"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/categories?post=1183"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/tags?post=1183"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}