C++:有哪些通用方法可以使代码更高效地处理大量数据？

Question

请在回答这个问题时尽可能笼统地帮助更广泛的社区，而不是仅仅专门帮助我的问题(尽管帮助我的问题也很好;))

我似乎在 Project Euler 上的简单问题中一次又一次地遇到这个问题。最常见的是需要计算素数的问题 - 对于大于 60,000 的数字，这些问题总是无法终止。

我最近的问题是问题 12:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 13: 1,36: 1,2,3,610: 1,2,5,1015: 1,3,5,1521: 1,3,7,2128: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

这是我的代码:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {

int numberOfDivisors = 500;

//I begin by looping from 1, with 1 being the 1st triangular number, 2 being the second, and so on.
for (long long int i = 1;; i++) {
    long long int triangularNumber = (pow(i, 2) + i)/2
    //Once I have the i-th triangular, I loop from 1 to itself, and add 1 to count each time I encounter a divisor, giving the total number of divisors for each triangular.
    int count = 0;
    for (long long int j = 1; j <= triangularNumber; j++) {
        if (triangularNumber%j == 0) {
            count++;
        }
    }
    //If the number of divisors is 500, print out the triangular and break the code. 
    if (count == numberOfDivisors) {
        cout << triangularNumber << endl;
        break;
    }
}

}

这段代码给出了较小数字的正确答案，然后要么无法终止，要么需要一段时间才能终止!

那么首先，我该如何处理这个特定问题才能使我的代码更有效率？

其次，对于我自己和其他 C++ 新用户来说，提高代码效率的一般技巧有哪些？ (即将来应用我们在这里学到的东西。)

谢谢!

Answer 1

关键问题是你的结束条件不好。你应该在 count > 500 时停止，但你正在寻找 count == 500 的精确匹配，因此你很可能在没有检测到它的情况下忽略了正确答案，并继续前进......也许永远。

如果你解决了这个问题，你可以将它发布到代码审查。他们可能会这样说:

将其分解为单独的函数以查找下一个三角形数，并计算某个数的因数。

当找到下一个三角形编号时，执行 pow。我执行一次加法。

要计算一个数字中的因子数量，谷歌搜索可能会有所帮助。 (例如 http://www.cut-the-knot.org/blue/NumberOfFactors.shtml)您可以随时构建一个素数列表，并使用它来快速找到一个素数分解，您可以从中计算因子的数量而无需实际计算它们。当数字变大时，循环变大。