Euler # 23项目c++代码的优化

Question

我正在解欧拉项目的问题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;
}

Answer 1

当前最大的优化是预先计算除数和。目前，您正在为每个factorsum(j)重新计算j = 12, ...的i。如果计算一次除数和并将其存储在数组中，则会成为快速(O(1))查找，而不是O(j/2)计算。

仅这一项，我的盒子上的运行时间就从3分半秒缩短到了1秒。

下一个改进是使用更好的策略来计算除数和。不需要在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秒。