{"id":1001,"date":"2014-09-05T10:11:16","date_gmt":"2014-09-05T17:11:16","guid":{"rendered":"http:\/\/www.coastalvectors.com\/blog\/?p=1001"},"modified":"2014-09-05T10:44:41","modified_gmt":"2014-09-05T17:44:41","slug":"project-euler-12","status":"publish","type":"post","link":"https:\/\/www.coastalvectors.com\/blog\/2014\/09\/project-euler-12\/","title":{"rendered":"Project Euler 12"},"content":{"rendered":"

I was recently going through some old Project Euler<\/a> solutions, and noticed that my solution to problem 12<\/a> was never optimized. The problems asks:<\/p>\n

The sequence of triangle numbers<\/a> is generated by adding the natural numbers. So the 7th<\/sup> triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:<\/p>\n

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …<\/p>\n

Let us list the factors of the first seven triangle numbers:<\/p>\n

1<\/b>: 1
\n3<\/b>: 1,3
\n6<\/b>: 1,2,3,6
\n10<\/b>: 1,2,5,10
\n15<\/b>: 1,3,5,15
\n21<\/b>: 1,3,7,21
\n28<\/b>: 1,2,4,7,14,28<\/p>\n

We can see that 28 is the first triangle number to have over five divisors.<\/p>\n

What is the value of the first triangle number to have over five hundred divisors?<\/p><\/blockquote>\n

The way I originally solved this problem was a brute-force approach following this basic logic:<\/p>\n

    \n
  1. Calculate next triangle number<\/li>\n
  2. Try dividing number by every integer smaller than the number<\/li>\n
  3. Count the number of integers that divide evenly<\/li>\n
  4. Go to step 1 and repeat until divisors are greater than 500<\/li>\n<\/ol>\n

    This process yielded the results, but it is far from elegant or optimized. it took 14 minutes<\/strong> to calculate the answer! I knew that dividing by each number was a waste; there had to be a better way.<\/p>\n

    Although I didn’t know it, I felt fairly certain that there was a relationship between prime factors and the number of divisors. It turns out I was right. There is a trick to calculate the number of divisors if you know the prime factors.<\/p>\n

    Using the number 28 as an example, we can find that the prime factors are 2, 2, and 7, which can be written as 22<\/sup> \u00d7 71<\/sup>. Interestingly, if we take the exponents, add 1 to each, and then multiply them together, we can calculate the number of divisors. For this example, this becomes (2+1) \u00d7 (1+1), which is 2 \u00d7 3, which equals 6. (This is also mentioned in the Wikipedia article for divisor<\/a> briefly in the section titled ‘Further notions and facts’<\/a>).<\/p>\n

    Equipped with this knowledge, I was able to devise a more efficient method to solve this problem:<\/p>\n

      \n
    1. Pre-calculate primes up to x amount (to save effort recomputing each time)<\/li>\n
    2. Calculate next triangle number that is divisible by 3 or 5 (I found a pattern that the most divisible triangle numbers were divisible by 3 or 5)<\/li>\n
    3. Go through primes and divide number by primes until number equals 1<\/li>\n
    4. Convert the prime factors to divisors<\/li>\n
    5. Go to step 1 and repeat until divisors are greater than 500<\/li>\n<\/ol>\n

      While this method is more complex, it yielded great results. Once I was done refining this method, I got the compute time down to .086 seconds<\/strong>. That is a very substantial improvement!<\/p>\n

      The interesting part of the code is the findDivisors function, seen below.<\/p>\n

      int findDivisors(int input, int *primes, int primesToFind)\r\n{\r\n    int i, count=1;\r\n    int primeCount[primesToFind];\r\n    for (i=0; i<primesToFind; i++)\r\n    primeCount[i] = 0;\r\n\r\n    \/\/ Prime factorization\r\n    while (input != 1)\r\n        for (i=0; i<primesToFind; i++)\r\n            if (input % primes[i] == 0)\r\n            {\r\n                input = input \/ primes[i];\r\n                primeCount[i]++;\r\n            }\r\n\r\n    \/\/ Convert prime factorization to divisors\r\n    for (i=0; i<primesToFind; i++)\r\n        if (primeCount[i] > 0)\r\n            count *= (primeCount[i]+1);\r\n\r\n    return count;\r\n}<\/code><\/pre>\n
      In this function, the inputs are:<\/p>\n