1

MathBlog で Project Euler Problem 12 の解決策を読んでいましたが、コードの背後にあるロジックを理解するのに苦労しています。プログラムは素因数分解を使用して、三角形の数の約数を見つけます。

private int PrimeFactorisationNoD(int number, int[] primelist) {
    int nod = 1;
    int exponent;
    int remain = number;

    for (int i = 0; i < primelist.Length; i++) {
        // In case there is a remainder this is a prime factor as well
        // The exponent of that factor is 1
        if (**primelist[i] * primelist[i] > number**) {
            return nod * 2;
        }

        exponent = 1;
        while (remain % primelist[i] == 0) {
            exponent++;
            remain = remain / primelist[i];
        }
        nod *= exponent;

        //If there is no remainder, return the count
        if (remain == 1) {
            return nod;
        }
    }
    return nod;
}

ハイライトされた部分「primelist[i] * primelist[i] > number」を除いて、プログラムのほとんどの部分を理解しています。このコード行の必要性を理解するのに苦労しています。私の要点を説明するために例を使用します。510 = 2*3*5*17 という数字があるとします。強調表示されたコードは、Primelist が 23 番に移動したときにのみ真になります。しかし、リストが 17 番に移動するまでに、条件は == 1 のままで真になり、プログラムはループを終了します。コードを if(remain==primelist[i]) に変更した方がよいでしょうか?なぜなら、primelist が 21 ではなく 17 になるとループが終了するからです。

4

2 に答える 2

0

まず、より適切に使用する必要がありますremain：

primelist[i] * primelist[i] > remain

remainとの平方根の間には除数がないため、これは最適化remainですremain。

また、変数名exponentは嘘をついており、実際には指数に 1 を加えたものが含まれています。ゼロに初期化し、 を掛けたほうがよいでしょうexponent + 1。

于 2013-05-18T07:32:14.813 に答える