0

当我在控制台中运行代码时，浏览器停止工作（假设堆栈溢出）。

我想出了几种不同的算法来解决这个问题，但我认为这个不会导致任何 SO。

问题：

三角形数的序列是通过添加自然数生成的。所以第 7 个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。前十项是：

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

让我们列出前七个三角形数的因数：

1:1

3：1 3

6：1,2,3,6

10：1,2,5,10

15：1,3,5,15

21: 1,3,7,21

28：1、2、4、7、14、28

我们可以看到 28 是第一个有五个以上除数的三角形数。

第一个有超过 500 个除数的三角形数的值是多少？

失败的解决方案：

function divisors(n){
    var counter = 0;
    var triangle = 3;
    var triangle_add = 2;
    while (counter < n){
        for (var i = 1; i = triangle; i++){
            if (triangle % i === 0){
                counter++;
            }
        };
        if (counter < n){
            triangle_add++;
            triangle = triangle + triangle_add;
            counter = 0;
        };
    };
    return triangle;
};

console.log(divisors(501));
4

1 回答 1

0

您的解决方案不起作用，因为很可能它非常慢。通过以下方法可以更快地解决此问题：

  1. 使用埃拉托色尼筛法找出所有小于某个 N 的素数（例如，输入 N=100'000）。它相当快。

  2. 正如我们从初等数学中知道的那样，每个数字都可以写成X=p1^i1*p2^i2*...*pn^in的形式，其中 pj 是素数，ij 是相应素数的幂。X 的除数等于(i1+1)*(i2+1)*...*(in+1)因为我们可以通过许多不同的方式形成一个将成为 X 的除数的数。拥有一个数组对于素数，X 的除数可以很快计算出来（代码还有待优化的地方）：

    int divisorCount(long long X)
{
    int c = 1;
    for (int i = 0; PRIMES[i] <= X; ++i)
    {
        int pr = PRIMES[i];
        if (X % pr == 0)
        {
            int p = 1;
            long long r = X;
            while (r % pr == 0)
            {
                r = r / pr;
                ++p;
            }
            c *= p;
        }
    }
    return c;
}

  3. 使用上述函数遍历所有三角形数并计算除数。第 i 个三角形数是i * (i + 1) / 2，因此无需保留变量，每次递增并添加它。

于 2013-08-26T21:29:48.290 回答