I was recently going through some old Project Euler solutions, and noticed that my solution to problem 12 was never optimized. The problems asks:
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
The way I originally solved this problem was a brute-force approach following this basic logic:
- Calculate next triangle number
- Try dividing number by every integer smaller than the number
- Count the number of integers that divide evenly
- Go to step 1 and repeat until divisors are greater than 500
This process yielded the results, but it is far from elegant or optimized. it took 14 minutes to calculate the answer! I knew that dividing by each number was a waste; there had to be a better way.
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.
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 × 71. 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) × (1+1), which is 2 × 3, which equals 6. (This is also mentioned in the Wikipedia article for divisor briefly in the section titled ‘Further notions and facts’).
Equipped with this knowledge, I was able to devise a more efficient method to solve this problem:
- Pre-calculate primes up to x amount (to save effort recomputing each time)
- 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)
- Go through primes and divide number by primes until number equals 1
- Convert the prime factors to divisors
- Go to step 1 and repeat until divisors are greater than 500
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. That is a very substantial improvement!
The interesting part of the code is the findDivisors function, seen below.
int findDivisors(int input, int *primes, int primesToFind)
{
int i, count=1;
int primeCount[primesToFind];
for (i=0; i<primesToFind; i++)
primeCount[i] = 0;
// Prime factorization
while (input != 1)
for (i=0; i<primesToFind; i++)
if (input % primes[i] == 0)
{
input = input / primes[i];
primeCount[i]++;
}
// Convert prime factorization to divisors
for (i=0; i<primesToFind; i++)
if (primeCount[i] > 0)
count *= (primeCount[i]+1);
return count;
}In this function, the inputs are:
- The triangle number (input)
- The array of pre-calculated prime numbers (primes)
- The number of primes in the array (primesToFind)
As the division of primes occurs, I keep track in a separate array (primeCount) how many times a given prime index is used to divide. This keeps track of the prime factorization I talked about earlier so we can finally compute the number of divisors. Once computed, we pass back the count, and the program moves on to the next triangle number.
So there you have it. My entire solution is available on my GitHub page.
