c# - 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);

score 5 · Accepted Answer

数が三角数であることは無視してください。この問題をすばやく解決できる場合:

任意の数 n が与えられた場合、それが持つ約数の数を決定します

明らかに、オイラー #12 をすばやく解くことができます。簡単に計算できる三角形の数を並べて、それぞれの約数を求め、結果が 500 以上になったら停止します。

では、どのようにして除数の数をすばやく決定するのでしょうか? お気づきのように、数字が大きくなると、大変な作業になります。

ここにヒントがあります。素因数分解がすでにあるとします。たとえば、196 という数字を選びましょう。それを素数に因数分解します。

196 = 2 x 2 x 7 x 7

素因数分解を見るだけで、196 には9 つの約数があることがわかります。どのように？

196 の約数は次の形式であるためです。

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

したがって、明らかに 9 つの可能な組み合わせがあります。

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

パターンが見えますか？素因数分解を行い、それらを素数でグループ化し、各グループに含まれる数を数えます。次に、これらの数値のそれぞれに 1 を加え、それらを乗算します。繰り返しますが、200 には素因数分解で3 つの2 と2 つの5 があります。それぞれに 1 を追加します: fourとthree。それらを掛け合わせる: 12 . これが約数の数です。

したがって、素因数分解がわかれば、約数をすぐに見つけることができます。除数の問題をはるかに簡単な問題に減らしました。素因数分解をすばやく行う方法を理解できますか?

score 2 · Accepted Answer

ここにいくつかの最適化を紹介します。

一番簡単なのは変えること

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 の約数を持つ最小の数を計算することです。

その後、最大の三角形の数を見つけて、そこから始めます。

この問題の性質について何か特別なことを理解できれば、ランタイムを大幅に短縮することができます。

score 1 · Accepted Answer

The number of divisors of a number is the product of the powers of the prime factors plus one. For example: 28 = 2^2*7^1, so the # of divisors is (2+1)*(1+1) = 6.

This means that, if you want many divisors compared to the size of the number, you don't want any one prime to occur too often. Put another way: it is likely that the smallest triangular number with at least 500 divisors is the product of small powers of small primes.

So, instead of checking every number to see if it divides the triangular number, go through a list of the smallest primes, and see how often each one occurs in the prime factorization. Then use the formula above to compute the number of divisors.

score 0 · Accepted Answer

@EricLippert と @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);
}

score 0 · Accepted Answer

次の手順を実行します。

1.) 最初の log(2, 499) 素数を計算します (約数が 1 つしかないため、素数ではないという事実にもかかわらず、私が間違っている場合、1 は約数としてカウントされるため、500 ではありません)。そこには多くの解決策がありますが、あなたは私のドリフトをキャッチします.

2.) 1 + 2 + ... + 100 = (1 + 100) + (2 + 99) + ... + (50 + 51) = 101 * 50 = 101 * 100 / 2 = 5050 (Cauchy が 8 歳のときにこの問題を解き、教師がこの問題で彼を罰したため)。

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

そして、そこに行きます。私があなたを助けることができたかどうか教えてください.

score -1 · Accepted Answer

ちなみに、検索クエリの最初のGoogle結果divisors of triangular numberはこれを与えます:)

Project Euler 12: 約数 500 の三角形数

それが役立つかどうかを確認してください。

編集：その記事のテキスト：

500 桁を超える最初の三角形の番号は次のとおりです: 76576500 解決に 1 ミリ秒かかりました

c# - C# 三角形の最適化

6 に答える 6

Related

Reference