1

私はプロジェクトオイラーの問題23を解決しています。私は単純なロジックを使用しました。正しい答えが得られていますが、プログラムの実行には非常に長い時間がかかります。

コードを最適化する方法はありますか？

私は最初に2つの豊富な数の合計であるすべての数を計算し、次にそれを全体の合計から差し引きます。

int factorsum(int);
int main()
{
    int i, j, s = 0, t, m;
    for (i = 24; i <= 28123; i++)   //sum of 2abundant nos start from 24
    {
        for (j = 12; j <= i / 2; j++) {
            t = factorsum(j);
            if (t > j) {
                m = i - j;
                t = factorsum(m);
                if (t > m) {
                    s = s + i;
                    break;
                }
            }
        }

    }
    j = 0;
    for (i = 1; i <= 28123; i++)
        j = j + i;
    printf("\n%d", (j - s));
    return 0;
}

int factorsum(int j)        //checking sum of factors
{
    int k, s = 0;
    for (k = 1; k <= (j / 2); k++) {
        if (j % k == 0) {
            s = s + k;
        }
    }
    return s;
}
4

1 に答える 1

2

差し迫った大きな最適化は、除数の合計を事前に計算することです。現時点では、ごとに再計算factorsum(j)しています。除数の合計を1回計算して配列に格納すると、計算ではなく高速（）ルックアップになります。j = 12, ...iO(1)O(j/2)

それだけで、私のボックスの実行時間が3分半から1秒に短縮されます。

次の改善は、除数の合計を計算するためのより良い戦略を使用することです。除数がペアになっているという事実を使用して、各数値j/2が除算されるかどうかを確認する代わりに、確認するだけで済みます（完全な平方に注意してください。平方根は、一度だけ追加する必要があります）。j(d, j/d)√j

それは0.05秒にそれを取ります。

nただし、合計を配列に格納する場合は、一度に1つの数値を考慮してその除数dを見つける代わりに、論理を逆にして1つの除数を考慮し、そのすべての倍数を見つけることで、さらにうまくいくことができます（ k*d）。これにより、除数の合計をからO(limit^1.5)（またはまでO(limit^2)除算した場合j/2）からに計算するために必要な時間が短縮されO(limit * log limit)ます。（注：絶対的な制限が与えられているため、ここでは複雑さの表記は厳密には適用されません。変数までの2つの豊富な数の合計ではない数を見つけようとしているとしましょうlimit。）

これで0.03秒になります。

于 2012-10-20T22:47:32.097 に答える