[C/C++] Project Euler #12 Highly Divisible Triangular Number

The problem is to find the first triangular number that has over 500 divisors. A triangular number is defined as the sum of natural numbers up to  n , calculated using the formula  \( T_n = \frac{n(n+1)}{2} \) . The task involves calculating triangular numbers and determining their divisors until one with more than 500 divisors is found.

 

triangular number

 

This code was written by me.

//------------------------------------------------
//    Project Euler #12 - Highly Divisible Triangular Number
//        - by Aubrey Choi
//        - created at 2014-12-29
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

#define    NUM    500

int GetNumDivisors(int n);

int solve1()
{
    int n = NUM;
    int a, b;

    b = GetNumDivisors(n++/2);
    for( ; ; )
    {
        a = GetNumDivisors(n++);
        if( a*b > NUM ) break;
        b = GetNumDivisors(n++/2);
        if( a*b > NUM ) break;
    }

    printf("Ans = %d\n", (n-2)*(n-1)/2);
}

int GetNumDivisors(int n)
{
    int c = 1;
    int k;

    for( k = 0 ; !(n%2) ; k++ ) n /= 2;
    c = k+1;
    for( int p = 3 ; p*p <= n ; p+=2 )
    {
        for( k = 0 ; !(n%p) ; k++ ) n /= p;
        c *= k+1;
    }
    return c*((n > 1)+1);
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}

 

The code solves the problem of finding the first triangular number with more than 500 divisors. It calculates triangular numbers using  \( T_n = \frac{n(n+1)}{2} \)  and checks their divisors using the GetNumDivisors function, which efficiently counts divisors through prime factorization. The solve1 function iteratively computes triangular numbers and their divisor counts until the condition  \( a \times b > 500 \)  is met, where  a  and  b  are the divisor counts of  n/2  and  n+1  (or vice versa).