c++ - Amicable Numbers : Runtime is to long. 是什么原因造成的？算法复杂度？

Question

我的代码有一点运行时问题。该代码运行良好，但在 Windows 上需要数十分钟，在 Linux 上需要数小时才能运行。

class AmicableNumbersBeta
{
private:
    long start;
    long end;
    std::vector<long> numbers;

protected:

    long getStart() { return start;}
    long getEnd() { return end;}

    void setStart(long start) {  this->start = start;}
    void setEnd(long end) {  this->end=end;}

    long SumOfDivisors(long value)
    {
        long result = 0;
        long half_value = value / 2;

        for (long i = 1; i <= half_value; i++)
        {

           if (value % i == 0)
           {
             result += i;
           }
        }

        return result;
    }

    void AddNumber(long value)
    {
        this->numbers.push_back(value);
    }

public:

    AmicableNumbersBeta(long Start, long End) : start(Start),end(End){}


       void Calculate()
       {
       // clear old calculation, if any
       this->numbers.clear();


       for (long i = getStart(); i < getEnd(); i++)
       {

           long s1 = SumOfDivisors(i);
           long s2 = SumOfDivisors(s1);

           if (s2 == i && i < s1)
           {
            std::cout<<"-- adding ( "<<i<<" )\n";
            this->AddNumber(i);
           }
       }
    }

};

如果我现在尝试运行这个程序，它开始计算 Alpha 直到 1000000 个数字，检查它确实需要几个小时。 但据我的老师说，计算应该只需要几秒钟。

int main() {
std::cout << "Hello, World!" << std::endl;

AmicableNumbersBeta Alpha(1,1000000);
AmicableNumbersBeta Beta( 1,100000);
AmicableNumbersBeta Gamma(1,10000);
AmicableNumbersBeta Delta(1,1000);

std::cout<<"Delta\n";
Delta.Calculate();

std::cout<<"\nGamma\n";
Gamma.Calculate();

std::cout<<"\nBeta\n";
Beta.Calculate();

std::cout<<"\nAlpha\n";
Alpha.Calculate();

std::cout << "Bye, World!" << std::endl;
return 0;
}

老实说，我不明白是什么导致了这种巨大的“延迟”。

我使用的平台是带有 GCC 4.9 的 Linux Debian和 Windows VS 15

如果有人能指出这种行为的原因，我将不胜感激。

Answer 1

如评论中所述，您的代码可以通过使用 memoization 以多种方式进行优化。或 sieves甚至并行性。

虽然在实际应用程序中，我可能会进行此类优化，但您在这里不需要这种“复杂”的东西 - 您只需要进行一次改进即可使您的代码在几秒钟而不是几分钟内运行:您需要计算除数最多为您的值的平方根。所以基本上:

long SumOfDivisors(long value)
{
    long result = 1; 

    for (long i = 2; i * i <= value; i++)
    {
       if (value % i == 0)
       {
           result += i;
           if (value / i != i) {
               result += value / i;
           }
       }
    }

    return result;
}

通过这个简单的修改，您可以在几秒钟内计算出高达 1000000 的友好数。