# Blog Archives

## Project Euler Problem#12 solution in C++

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^{th} 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,28

We 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?

**Solution:**

#include <cstdio> #include <cmath> int numDivisors(int num) { int divisors = 1, exp; //handle 2 and 3 as special case exp = 0; while (num % 2 == 0) { num /= 2; exp++; } divisors *= (exp+1); exp = 0; while (num % 3 == 0) { num /= 3; exp++; } divisors *= (exp+1); //the other primes are 6k +/- 1 int i = 5; int root = floor(sqrt(num)); while (i <= root) { exp = 0; while (num % i == 0) { num /= i; exp++; } divisors *= (exp+1); if (i % 6 == 1) i += 4; else i += 2; root = floor(sqrt(num)); } //a single largest prime factor if (num != 1) divisors *= 2; return divisors; } int main(void) { int n = 0; int divisors = 0; while (divisors <= 500) { //while (n <= 10) { n++; //since t = n*(n+1)/2 and gcd(n,n+1)=1 if (n % 2 == 0) divisors = numDivisors(n/2) * numDivisors(n+1); else divisors = numDivisors(n) * numDivisors((n+1)/2); } printf("%d - %ld: %d\n", n, (long)n*(n+1)/2, divisors); }

###### Related articles

- Project Euler Problem#10 solution in C++ (alikhuram.wordpress.com)
- Project Euler problem#9 solution in C++ (alikhuram.wordpress.com)
- What is Pascal’s Triangle?, Part 2 (scientificamerican.com)