親和性のある数字：実行時間は長くなります。それは何が原因でしょうか？アルゴリズムの複雑さ？

Question

私は自分のコードで少しのランタイム問題があります。コードは正常に動作しますが、Windowsでは数十分、Linuxでは数時間かかることがあります。

このプログラムを今すぐ実行しようとすると、アルファティル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; 
} 

私は正直、この巨大な「遅延」を引き起こす可能性があるかを理解していません。私が使用

プラットフォームは15

GCC 4.9 とLinuxのDebianとWindowsのVSいる誰かが、この行動の理由を指摘することができれば、私は本当にいただければ幸いです。

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までの数を数秒で計算することができます。