C 程序运行异常缓慢

Question

我用 C 语言编写的一个简单程序需要半小时以上才能运行。我很惊讶 C 需要这么长时间才能运行，因为根据我在互联网上可以找到的信息，C(除了 C++ 或 Java)是一种更快的语言。

// 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;
}

虽然程序运行了很多数据，但没有一个被保存，只是测试并通过了。

我在 Windows 8 上使用 Tiny C 编译器。

运行这么慢有什么原因吗？达到相同结果的更快方法是什么？

谢谢!

Answer 1

您正在迭代大量不需要的数字。根据定义，正因子是可以与另一个整数相乘以获得所需乘积的任何整数。

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

决定因素时不考虑乘法顺序。换句话说，

Ex: 12 = 2*6 = 6*2

顺序无关紧要。 2 和 6 是一次的因子。

平方根是从一个独立产品的因式分解中得出的一个单例。所有其他人都是成对的，我希望这是清楚的。鉴于此，您可以通过执行以下操作显着加快代码速度:

#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;
}

运行此 on IDEOne.com只需不到两秒钟即可得出以下结论:

输出

76576500 is the first triangular number with more than 500 factors

希望对您有所帮助。 (我认为这是正确答案)。当然有更有效的方法来做到这一点(see here 如果您有兴趣的话，对于一些剧透)，但是按照您的代码想法并看看我们能走多远是这个答案的目标。

最后，这会根据您的输出消息找到第一个因子超过 500(即 501 或更多)的数字。您在文件顶部的评论表明您正在寻找第一个 500 或更多的数字，这与您的输出消息不匹配。