C# 三角数优化

Question

任务是找到至少有 500 个因数的三角形数。

例如 28 有 6 个除数:1,2,4,7,14,28

我的代码最多适用于 200 个除数，但对于 500 个它会永远运行...

有没有办法优化代码。例如，我想到了动态优化和记忆化，但找不到实现的方法？

            int sum = 0;
            int counter = 0;
            int count = 1;

            bool isTrue = true;
            while (isTrue)
            {
                counter = 0;
                sum += count;

                for (int j = 1; j <= sum; j++)
                {
                    if (sum % j == 0)
                    {
                        counter++;
                        if (counter == 500)
                        {
                            isTrue = false;
                            Console.WriteLine("Triangle number: {0}", sum);
                            break;
                        }
                    }
                }
                count++;
            }            
            Console.WriteLine("Number of divisors: {0}", counter);

Answer 1

忽略数字是三角形数字的事实。如果你能快速解决这个问题:

• 给定任意数n，求它的约数个数

那么显然您可以快速求解 Euler #12。只需列出易于计算的三角形数，确定每个三角形的除数，并在得到 500 或更大的结果时停止。

那么如何快速确定除数的个数呢？正如您所发现的，当数字变大时，需要做很多工作。

这是一个提示。假设您已经有了质因数分解。让我们选择一个数字，比如 196。将其分解为素数:

196 = 2 x 2 x 7 x 7

只要看一眼因式分解，我就可以告诉你 196 有 9 个因数。怎么办？

因为 196 的任何除数都是以下形式:

(1, 2 or 2x2) x (1, 7 or 7x7)

显然有九种可能的组合:

1 x 1
1 x 7
1 x 7 x 7
2 x 1
2 x 7
2 x 7 x 7
2 x 2 x 1
2 x 2 x 7
2 x 2 x 7 x 7

选择另一个号码。 200，可以说。那是 2 x 2 x 2 x 5 x 5。所以有 12 种可能性:

1 x 1
1 x 5
1 x 5 x 5
2 x 1
2 x 5
...
2 x 2 x 2 x 5 x 5

看到图案了吗？您进行质因数分解，将它们按质数分组，然后计算每组中有多少。然后你将这些数字中的每一个加一并将它们相乘。同样，在 200 中，素数分解中有三个 个二和两个 个五。每个加一个:四个和三个。将它们相乘:十二。这就是除数的数量。

因此，如果您知道质因数分解，就可以很快找到除数。我们已将除数问题简化为更简单的问题:你能想出如何快速产生质因数分解吗？