patterncppMinorCanonical

Project Euler #12 - highly divisible triangular number

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

codereview cpp c++stackoverflow optimization c++11 programming-challenge algorithm

numberhighlydivisibleprojecteulertriangular

Problem

The following is a solution to Project Euler problem number 12: which is to find the first triangular number with more than 500 divisors.

The code takes far too long to complete (over 10 minutes). Is there any way to optimize the run-time and to make it more elegant?

#include 
#include 
#include 

inline void triangle(int &num, int &interval)
{
    num = ((interval * interval) + interval ) / 2;
}

int main()
{
    long int input;
    int num = 1, interval = 1, divisor = 1, no_divisor = 0;

    std::cout > input;

    auto start = std::chrono::steady_clock::now();

    for (;;)
    {
        while (divisor  input) //divisor count over input number, jump to exit;
                {
                    goto exit;
                }
            }
            divisor++;
        }
        std::cout (end - start);

    std::cout << "\nIt took me " << elapsed.count() << " milliseconds." << "\n";

    return 0;
}

Optimization I've done:

using std::cout

using inline void triangle(int &num, int &interval)` speed up 10% time

using n(n+1)/2 according to this

Speculation:

I figured if the question asked for over 500 factors, which for example:
Triangular number 28 has over 5 factors:

So I only need to iterate up to half of the limit. But how can I implement that into my code to only iterate up to half as many factor?

Solution

Project Euler problems typically don't benefit from micro-optimizations such as inlining functions or flushing standard output. The biggest speed gains often come from algorithmic improvements. Here there are two key mathematical facts that can make this computation tractable:

A number with prime factorisation n = Product_i p_i ^ e_i (where p_i are primes and e_i their exponents) has a number of divisors equal to d = Product_i (e_i + 1).

A triangle number is equal to n * (n + 1) / 2. These factors have no prime factors in common and only one of them has a factor of two. This means that the number of divisors of a triangle number can be factored in the number of the divisors of n and n+1.

In order to code this algorithm, a few more guidelines to writing better code:

write functions that take an int and return an int. Don't use Pascal like procedures by modifying a reference argument. This makes your code harder to reason about.

separate computation from I/O: an algorithm should ideally have no side effects, and be silent. If you want to query the result, just print that.

Below some working code:

#include 
#include 
#include 

int triangle(int n)
{
    return ((n + 1) * n) / 2;    
}

// Math fact: a prime decomposition n = Prod_i p_i^e_i yields
// Prod_i (e_i + 1) different divisors
int num_divisors(int n)
{
    auto divisors = 1;  // 1 has one divisor
    {
        auto f = 2;
        auto count = 0;
        while (n % f == 0) {
            ++count;
            n /= f;     // divide by factor of 2
        }
        divisors *= (count + 1);
    }

    // (stop - start);

    std::cout << "\nIt took me " << elapsed.count() << " milliseconds." << "\n";
}

Live Example that runs in less than 0.2 seconds.

Code Snippets

#include <chrono>
#include <ctime>
#include <iostream>

int triangle(int n)
{
    return ((n + 1) * n) / 2;    
}

// Math fact: a prime decomposition n = Prod_i p_i^e_i yields
// Prod_i (e_i + 1) different divisors
int num_divisors(int n)
{
    auto divisors = 1;  // 1 has one divisor
    {
        auto f = 2;
        auto count = 0;
        while (n % f == 0) {
            ++count;
            n /= f;     // divide by factor of 2
        }
        divisors *= (count + 1);
    }

    // <= n guarantees that a prime has 2 divisors
    for (auto f = 3; f <= n; f += 2) {
        auto count = 0;
        while (n % f == 0) {
            ++count;
            n /= f;     // divide by odd factor
        }
        divisors *= (count + 1);
    }
    return divisors;
}

int unique_divisors(int n)
{
    if (n % 2 == 0)
        n /= 2;
    return num_divisors(n);
}

// triangle(n) = (n + 1) * n / 2
// only one of them has a factor of two, and they have no prime factors in common
// we can cache one of the divisor counts while iterating over triangle numbers
int first_triangle_with_more_than_n_divisors(int n)
{
    auto i = 1;
    for (auto f1 = unique_divisors(i), f2 = unique_divisors(i + 1); f1 * f2 <= n; ++i)   {
        f1 = f2;                        // re-use result from previous iteration
        f2 = unique_divisors(i + 2);    // only one new computation
    }
    return i;
}

int main()
{
    auto start = std::chrono::steady_clock::now();

    auto const n = 500;
    auto res = first_triangle_with_more_than_n_divisors(n);

    std::cout << "the first Triangle number to have over " << n << " divisors : " << triangle(res) << "\n";

    auto stop = std::chrono::steady_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);

    std::cout << "\nIt took me " << elapsed.count() << " milliseconds." << "\n";
}

Context

StackExchange Code Review Q#39373, answer score: 3

Revisions (0)

No revisions yet.