0

コンソールでコードを実行すると、ブラウザーが機能しなくなります (スタック オーバーフローを想定しています)。

この問題を解決するためにいくつかの異なるアルゴリズムを考え出しましたが、これは SO を引き起こさないと思いました。

問題：

三角形の数列は、自然数を加算することによって生成されます。したがって、7 番目の三角形の数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 になります。最初の 10 項は次のようになります。

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

最初の 7 つの三角形の数の因数を挙げてみましょう。

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 は、約数が 5 を超える最初の三角形の数であることがわかります。

約数が 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 に答える