1

我正在解决项目 euler 的第 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)为j = 12, ...每个i. 如果您计算一次除数和并将它们存储在一个数组中，这将成为快速 ( O(1)) 查找而不是O(j/2)计算。

仅此一项就将我的盒子上的运行时间从三分半钟减少到一秒。

下一个改进将是使用更好的策略来计算除数和。您可以使用除数成对出现的事实来检查每个数字，而不是检查每个数字j/2是否相除（注意完美的平方，您只能将平方根相加一次）。j(d, j/d)√j

这将其缩短到 0.05 秒。

但是，如果您将总和存储在一个数组中，您可以通过颠倒逻辑做得更好，而不是一次考虑一个数字n并找到它的除数，而是考虑一个除数d并找到它的所有倍数 ( k*d)。这减少了计算从O(limit^1.5)（或者O(limit^2)如果你除以j/2）到的除数总和所需的时间O(limit * log limit)。（注意：由于给定了一个绝对限制，复杂性符号在这里并不严格适用，让我们假设您尝试找到不是两个丰富数字之和的数字，直到一个变量limit。）

这使它成为0.03秒。

于 2012-10-20T22:47:32.097 回答