A C program to find all factorions using a hash table The objective of this program is to find all factorions, which are numbers equal to the sum of the factorials of their digits.

I am seeking suggestions on how to improve the performance of this code, as well as stylistic advice.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#define base 10 //We are working in base 10
#define upper_bound 2540160 //This is 7 x 9! because a factorion can have at most seven digits.
//If it has d digits, it must satisfy the inequality 10^{d-1} &lt; n &lt;= 9!d, which isn't satisfied above d = 8
#define expected_no_of_answers 5 //I chose 5 somewhat arbitrarily. I knew beforehand there are only four answers in base 10

//Function prototype
void create_hash_table(int[]);
void get_fact_digit_sum(int[],int[]);
void display_answers(int[]);

int main()
{
    int hash_table_fact[base], answers[expected_no_of_answers]; //Creating a hash table where t[n] -&gt; n!

    create_hash_table(hash_table_fact);

    get_fact_digit_sum(answers,hash_table_fact);

    display_answers(answers);

    return 0;
}

void create_hash_table(int hash_table_fact[])
{       
    int i = 1, fact = 1;
    hash_table_fact[0] = 1; //0! = 1

    for(i = 1; i &lt; base; i++)
    {
        fact = fact*i;
        hash_table_fact[i] = fact;
    }
}

void get_fact_digit_sum(int answers[], int hash_table_fact[])
{
    int answerCount = 0, i = 1, temp, sum;

    //Combing through the search space to search for factorions
    for(i = 1; i &lt;= upper_bound; i++)
    {
        temp = i;
        sum = 0;
        //Getting the sum of the factorials of the digits
        while(temp != 0)
        {
            sum = sum + hash_table_fact[ (temp%base) ];
            temp = temp/base;
        }
        if(sum == i)
        {
            answers[answerCount++] = i;
        }
    }

    //Placing a 0 at the end to mark the end of the array
    answers[answerCount] = 0;
}

void display_answers(int answers[])
{
    int i;

    for(i = 0; answers[i] != 0; i++)
    {
        printf("%d\t",answers[i]);
    }
}
You can use the previous sum to compute the next one

Your main loop computes the sum of factorials of digits from scratch for each number, but you are throwing away a lot of work from number to number.  Think about two consecutive numbers, such as:

1234: sum = 1! + 2! + 3! + 4!
1235: sum = 1! + 2! + 3! + 5!


You can see that for 1235, it only differs from 1234 by the last digit, so you can compute its sum more quickly if you do this:

sum = previousSum + 5! - 4!


If the last digit wraps around from 9 to 0, you have to do the same thing with the next digit on the left:

1239: sum = 1! + 2! + 3! + 9!
1240: sum = 1! + 2! + 4! + 0!

sum  = previousSum;
sum += 0! - 9! // Ones digit
sum += 4! - 3! // Tens digit


If you reach a new power of 10, you need to do something a little different:

 99: sum =      9! + 9!
100: sum = 1! + 0! + 0!

sum  = previousSum;
sum += 0! - 9! // Ones digit
sum += 0! - 9! // Tens digit
sum += 1!      // Hundreds digit (note: do not subtract 0!)


Sample rewrite

Using this idea, your function becomes this:

void get_fact_digit_sum(int answers[], int hash_table_fact[])
{
    int answerCount = 0;
    int sum         = 1;

    // Combing through the search space to search for factorions
    for (int i = 1; i &lt;= upper_bound; i++) {
        int temp = i;

        while (1) {
            int digit = temp % base;
            if (digit == 0) {
                sum += hash_table_fact[0] - hash_table_fact[base-1];
                temp /= base;
                if (temp == 1) {
                    // Special case: reached new digit.
                    sum += hash_table_fact[1];
                    break;
                }
            } else {
                sum += hash_table_fact[digit] - hash_table_fact[digit-1];
                break;
            }
        }
        if (sum == i) {
            answers[answerCount++] = i;
        }
    }

    // Placing a 0 at the end to mark the end of the array
    answers[answerCount] = 0;
}


The new way ran 4x faster than the old way for the given upper bound.  If you extend the upper bound to 100 million (even though there are no answers that high), the new way runs 8x faster than the old way.