Euler 5

euler5.c

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

typedef unsigned long ul;

/*
 * Factors n into primes
 *
 * Returns a pointer to an array of 
 * unsigned longs. This needs to be
 * freed.
 *
 * Also the size of the array is put
 * in the nfactors parameter.
 */
ul *factor(ul n, int *nfactors) {
    ul *array = (ul *) NULL;
    int array_size = 0;

    ul i = 2;
    while (n > 1) {
        if (n % i == 0) {
            array = (ul *)realloc(array, ++array_size * sizeof(ul));
            array[array_size - 1] = i;
            n /= i;
            i = 2;
        } else {
            ++i;
        }
    }

    *nfactors = array_size;
    return array;
}

/*
 * Counts the occurances of the needle
 * in the array.
 */
int count(ul *array, int size, ul needle) {
    int i;
    int count = 0;
    for (i = 0; i < size; ++i) {
        if (array[i] == needle)
            ++count;
    }
    return count;
}

/*
 * Helper function for qsort
 */
int compare (const void * a, const void * b)
{
      return ( *(ul*)a - *(ul*)b );
}

/* 
 * Gets the smallest number that is
 * divisible by all the numbers 1 - n
 */
ul euler5(ul n) {
    ul *array = (ul *)NULL;
    int asize = 0;
    ul cur;

    /* Factoring all numbers 1 - n, starting at n
     * and going down. */
    for (cur = n; cur > 1; --cur) {
        int nfactors;
        ul *factors = factor(cur, &nfactors);
        qsort(factors, nfactors, sizeof(ul), compare);

        /* Add factors to the array. */
        int j = 0;
        while (j < nfactors) {
            int fc = count(factors, nfactors, factors[j]);
            int ac = count(array, asize, factors[j]);

            /* Adds the number of factors the array 
             * is missing. */
            int diff = fc - ac;
            if (diff > 0) {
                asize += diff;
                array = (ul *)realloc(array, asize * sizeof(ul));
                int k = 0;
                for (k = asize - diff; k < asize; ++k)
                    array[k] = factors[j];
            }
            j += fc;
        }
        free(factors);
    }

    /* Build the number from the factors we found. */
    int i;
    ul p = 1;
    for (i = 0; i < asize; ++i)
        p *= array[i];

    free(array);
    return p;
}

int main(int argc, char **argv) {
    if (argc != 2) {
        printf("Usage: %s number.\n", argv[0]);
        return 1;
    }

    ul n = strtoul(argv[1], NULL, 0);
    ul p = euler5(n);

    printf("%lu\n", p);

    return 0;
}