適切な除数の合計N

Question

N（N < = 20000000）までの適切な除数の和を求めなければなりません。私は複雑さO（N * log（N））でこの関数をあらかじめ計算しています。これは最大4秒かかります。それを最適化するにはどうすればよいのでしょうか。

例：N = 10答えが86であり、N = 1000の答えが823080

int f(){ 
    for(LL i = 1; i <= m; i++){ 
     for(LL j = i; j <= m; j += i){ 
      ans[j] += i; 
     } 
    } 
    for(LL i = 2; i <= m; i++)  ans[i] += ans[i - 1]; 
} 

あるIはまた、素因数分解とthis式を使用してみましたが、それは、アルゴリズム上よりも時間がかかります。

Answer 1

私の以前のコメントは編集できません。私のコメントで参照される問題は少し異なりますが、マイナーな調整でこの質問にも答えます。 ループ内で除数自体を掛けるだけです。