0

我用 C 编写的一个简单程序需要半小时以上才能运行。我很惊讶 C 需要这么长时间才能运行，因为从我在 Internet 上可以找到的内容来看，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 编译器。

运行如此缓慢是否有原因？实现相同结果的更快方法是什么？

谢谢！

4

5 回答 5

2

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

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

在 IDEOne.com 上运行此程序只需不到两秒钟即可得出以下结果：

输出

76576500 is the first triangular number with more than 500 factors

我希望这有帮助。（我认为这是正确的答案）。当然有更有效的方法可以做到这一点（如果您有兴趣，请参阅此处的一些剧透），但是按照您的代码想法并看看我们能走多远是这个答案的目标。

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

于 2013-08-17T20:36:50.470 回答
1

没有任何数学分析：

  ...

  do 
  {   
    c = 0;
    t += b;
    b++;

    for (d = 1; d < t; ++d)
    {       
      if (!(t % d))
      {
        c++;
      }       
    }
  } while (c <= 500);

  ...
于 2013-08-17T19:01:11.940 回答
1

您正在实现 O(n^2) 算法。如果代码花费不到半小时，那将是令人惊讶的。

与以下蛮力方法相比，请参阅您的计算机科学教科书以获得更好的方法：检查 1、1 + 2、1 + 2 + 3 等。

您也许可以缩短内部 for 循环。是否真的需要一直检查直到 t 的因子来划分三角形数。例如，10 能被任何大于 5 的数整除吗？还是 100 乘任何大于 50 的数？

因此，给定一个数 N，能将 N 整除的最大数是多少？继续阅读/研究这个问题。

此外，正如其他人所提到的，外循环可以简单地编码为：

  while (1)
  {
    // etc.
  }

所以，不需要声明e，或者a？请注意，这不会影响时间长度，但您的编码风格表明您仍在学习，因此审阅者会质疑您的代码所做的一切！

于 2013-08-17T20:29:22.303 回答
0

三角形数的美妙之处之一是，如果你有一个三角形数，通过简单的加法运算，你就可以拥有下一个。

于 2013-08-17T20:39:41.513 回答
0

您正在做一些不必要的操作，如果我们可以简单地检查，我认为这些说明根本不需要。

第一的 ：

while(e!=0)

正如您所声明e=1的，如果您只1放入循环中，它将起作用。您没有更新e任何地方的价值。

更改它并检查它是否工作正常。

于 2013-08-17T19:00:06.023 回答