C Program Runs Surprisingly Slow

A simple program I wrote in C takes upwards of half an hour to run. I am surprised that C would take so long to run, because from what I can find on the internet C ( aside from C++ or Java ) is one of the faster languages.

// this is a program to find the first triangular number that is divisible by 500 factors

int main()
{
    int a; // for triangular num loop
    int b = 1; // limit for triangular num (1+2+3+......+b)
    int c; // factor counter
    int d; // divisor
    int e = 1; // ends loop
    long long int t = 0; // triangular number in use

    while( e != 0 )
    {   
        c = 0;

        // create triangular number t
        t = t + b;
        b++;

        // printf("%lld\n", t); // in case you want to see where it's at
        // counts factors
        for( d = 1 ; d != t ; d++ )
        {       
            if( t % d == 0 )
            {
                c++;
            }       
        }

        // test to see if condition is met
        if( c > 500 )
        {
            break;  
        }
    }

    printf("%lld is the first triangular number with more than 500 factors\n", t);

    getchar();
    return 0;
}

Granted the program runs through a lot of data, but none of it is ever saved, just tested and passed over.

I am using the Tiny C Compiler on Windows 8.

Is there a reason this runs so slowly? What would be a faster way of achieving the same result?

Thank you!

Solution

You're iterating over a ton of numbers you don't need to. By definition, a positive factor is any whole number that can be multiplied by another to obtain the desired product.

Ex: 12 = 1*12, 2*6, and 3*4

The order of multiplication are NOT considered when deciding factors. In other words,

Ex: 12 = 2*6 = 6*2

The order doesn't matter. 2 and 6 are factors once.

The square root is the one singleton that will come out of a factoring of a product that stands alone. All others are in pairs, and I hope that is clear. Given that, you can significantly speed up your code by doing the following:

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

// this is a program to find the first triangular number that is divisible by 500 factors

int main()
{
    int c = 0;                  // factor counter
    long long int b = 0;        // limit for triangular num (1+2+3+......+b)
    long long int d;            // divisor
    long long int t = 0;        // triangular number in use
    long long int r = 0;        // root of current test number

    while (c <= 500)
    {
        c = 0;

        // next triangular number
        t += ++b;

        // get closest root.
        r = floor(sqrt(t));

        // counts factors
        for( d = 1 ; d < r; ++d )
        {
            if( t % d == 0 )
                c += 2;  // add the factor *pair* (there are two)
        }
        if (t % r == 0)  // add the square root if it is applicable.
            ++c;
    }

    printf("%lld is the first triangular number with more than 500 factors\n", t);
    return 0;
}

Running this on IDEOne.com takes less than two seconds to come up with the following:

Output

76576500 is the first triangular number with more than 500 factors

I hope this helps. (and I think that is the correct answer). There are certainly more efficient ways of doing this (see here for some spoilers if you're interested), but going with your code idea and seeing how far we could take it was the goal of this answer.

Finally, this finds the first number with MORE than 500 factors (i.e. 501 or more) as per your output message. Your comment at the top of the file indicates you're looking for the first number with 500-or-more, which does not match up with your output message.