C Developer: Project Euler problem 12

Project Euler problem 12

Find the first triangle number with over 500 factors.

Solution

Generating a list of triangular numbers is trivial, as we start from 1 and add a step of 2, incrementing the step each time. The first 1mn can be generated with:

int triangle_number = 0;
int step = 0;

for (triangle_number = 1, step = 2; triangle_number < 1000000 triangle_number += step, step++) {
    printf("%d\n", triangle_number);
}

We also need a way of counting the factors for a given number. The simplest way would be to attempt to divide n by every number from 1 to n. However, every factor f must have a paired factor f', such that f x f' = n. This means that we only need to divide n by every number from 1 to the square root of n, and add 2 to the factor count each time there is no remainder. The only edge case we have to consider is when f = f', which will only happen when f is the square root of n. In this case we only count the factor once.

We can write a short function to do this:

int count_factors(int factorise) {
    int factor_count = 0;
    int possible_factor = 0;
    int other_factor = 0;
    int upper_bound = (int) floor(sqrt(factorise));

    for (possible_factor = 1; possible_factor <= upper_bound; possible_factor++) {
        if (factorise % possible_factor == 0) {
            factor_count++;

            other_factor = factorise / possible_factor;
            if (other_factor != possible_factor) {
                factor_count++;
            }
        }
    }

    return factor_count;
}

The only line worthy of comment is:

int upper_bound = (int) floor(sqrt(factorise));

This will cause a warning to be emitted if -Wbad-function-cast is used, either explicitly or via -Weverything (it is not included in -Wall or -Wextra). This is because there may be numbers that can be stored in a double but not an int, and therefore the cast is potentially unsafe.

The full solution is:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdbool.h>

#define FACTOR_COUNT_TARGET 500

static int count_factors(int factorise) {
    int factor_count = 0;
    int possible_factor = 0;
    int other_factor = 0;
    int upper_bound = (int) floor(sqrt(factorise));

    for (possible_factor = 1; possible_factor <= upper_bound; possible_factor++) {
        if (factorise % possible_factor == 0) {
            factor_count++;

            other_factor = factorise / possible_factor;
            if (other_factor != possible_factor) {
                factor_count++;
            }
        }
    }

    return factor_count;
}

int main() {
    int triangle_number = 0;
    int step = 0;
    bool target_met = false;

    for (triangle_number = 1, step = 2; !target_met; triangle_number += step, step++) {
        if (count_factors(triangle_number) > FACTOR_COUNT_TARGET) {
            target_met = true;
            printf("%d\n", triangle_number);
        }
    }

    return EXIT_SUCCESS;
}

Note that the count_factors function has been made static to indicate that it is not called from outside this compilation unit.