合适的除数N的总和

我必须找到合适的除数N（N < = 20000000）。我已经预先计算了复杂度为O（N * log（N））的这个函数，这需要4秒钟。我如何优化它或任何备用解决方案将被大力接受。合适的除数N的总和

实施例：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]; 
}

我也使用质数分解和this式试过，但它需要更多的时间比上述算法。

来源

2016-04-28 Jobayer sheikh

此问题已得到很好的回答： http://stackoverflow.com/questions/7323572/how-to-find-total-number-of-divisors-upto-n/8337647#8337647 – emilio

我不能编辑我以前的评论，只是说我的评论引用的问题有点不同，但稍作调整就能回答这个问题。只需在除数内部乘以循环内部即可。

来源

2016-05-05 15:37:25 emilio

合适的除数N的总和

回答

相关问题