1

任务是找到一个至少有 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);
4

6 回答 6

5

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

  • 给定任意数 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。所以有十二种可能性：

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中，在素因数分解中有三个二和两个五。各加一：四和三。将它们相乘：十二。那就是有多少个除数。

因此，如果您知道素因数分解，您可以很快找到除数的数量。我们已经将除数问题简化为一个更简单的问题：你能弄清楚如何快速生成素数分解吗？

于 2013-03-11T20:00:05.173 回答
2

这里有一些优化，我会为你扔掉。

最简单的就是改变

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

如果你找到了 1 个除数，你就找到了 2 个除数，所以把它改成

for (int j = 1; j <= sum; j++)
{
    if (sum % j == 0)
    {
        if(sum/j < j)
            break;
        else if(sum/j == j)
            counter++;
        else
            counter +=2;

        if (counter == 500)
        {
            isTrue = false;
            Console.WriteLine("Triangle number: {0}", sum);
            break;
        }
    }
}

这将大大减少运行时间，但仍然需要很长时间。

您可以做的另一个优化是不开始检查表格sum，而是计算具有 500 个除数的最小数字。

然后你可以找到最大的三角形数，然后从那里开始。

如果您能找出有关此问题性质的其他特别之处，那么您可能会大大减少运行时间。

于 2013-03-11T18:56:42.137 回答
1

一个数的除数是质因数的幂加一的乘积。例如：28 = 2^2*7^1，所以除数的 # 是(2+1)*(1+1) = 6。

这意味着，如果与数字的大小相比，您想要许多除数，您不希望任何一个素数出现得太频繁。换句话说：具有至少 500 个除数的最小三角数很可能是小素数的小幂的乘积。

因此，与其检查每个数是否能整除三角形数，不如查看一个最小素数列表，看看每个素数在素数分解中出现的频率。然后使用上面的公式计算除数的数量。

于 2013-03-11T22:20:49.500 回答
0

采取以下步骤：

1.) 计算第一个 log(2, 499) 素数（不是 500，因为如果我弄错了 1 被视为除数，尽管它不是素数，因为它只有一个除数）。那里有很多解决方案，但你明白我的意思。

2.) 三角形数的形式为 n * (n + 1) / 2，因为 1 + 2 + ... + 100 = (1 + 100) + (2 + 99) + ... + (50 + 51) = 101 * 50 = 101 * 100 / 2 = 5050（柯西在他八岁的时候就解决了这个问题，老师用这个任务惩罚了他）。

1 + ... + n = (1 + n) + (2 + n - 1) + ... = n * (n + 1) / 2。

3.) S = prod(第一个 log(2, 499) 素数)

4.) 求解 n * (n + 1) / 2 = S 的方程并计算其上限。你将有一个整数，我们称它为 m。

5.)

while (not(found))
    found = isCorrect(m)
    if (not(found)) then
        m = m + 1
    end if
end while
return m

你去吧。如果我能帮助你，请告诉我。

于 2013-03-11T22:13:37.197 回答
0

正如@EricLippert nad @LajosArpad 提到的那样，关键思想是仅迭代三角形数字。您可以使用以下公式计算它们：

T(n) = n * (n + 1) / 2

这是JSFiddle，您可能会发现它很有帮助。

function generateTriangleNumber(n) {
    return (n * (n + 1)) / 2;
}

function findTriangleNumberWithOver500Divisors() {
    var nextTriangleNum;
    var sqrt;
    for (i = 2;; i++) {
        var factors = [];
        factors[0] = 1;
        nextTriangleNum = generateTriangleNumber(i);
        sqrt = Math.pow(nextTriangleNum, 0.5);
        sqrt = Math.floor(sqrt);
        var j;
        for (j = 2; j <= sqrt; j++) {
            if (nextTriangleNum % j == 0) {
                var quotient = nextTriangleNum / j;
                factors[factors.length] = j;
                factors[factors.length] = quotient;
            }
        }
        factors[factors.length] = nextTriangleNum;
        if (factors.length > 500) {
            break;
        }
    }
    console.log(nextTriangleNum);
}
于 2013-05-27T06:01:34.650 回答
-1

顺便说一句，搜索查询的第一个谷歌结果给出了这个:)divisors of triangular number

Project Euler 12：具有 500 个除数的三角形数

看看有没有帮助。

编辑：那篇文章的文字：

第一个超过 500 位的三角形数是：76576500 求解耗时 1 ms

于 2013-03-11T19:24:03.730 回答