Docs


Problem 12: Highly divisible triangular number

Problem

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, 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

/*
 * Highly divisible triangular number
 * Problem 12 <https://projecteuler.net/problem=12>
 *
 * Project Euler
 *
 * By Ankit R Gadiya
 */

#include <stdio.h>

int tri_num_gen (int x)
{
	return ((x * (x - 1)) / 2);
}

int divisors (long int num)
{
	int fact = 2, no_of_fact = 0;

	while (fact * fact <= num) {
		if (num % fact == 0)
			no_of_fact += 2;

		fact++;
	}

	return no_of_fact;
}

int main (void)
{
	int num = 0;
	long int tri_num;

	while (1) {
		num++;
		tri_num = tri_num_gen(num + 1);
		if (divisors(tri_num) >= 500)
			break;
	}

	printf("%ld\n", tri_num);

	return 0;
}

prob12.c

Result

76576500