読者です 読者をやめる 読者になる 読者になる

かもメモ

自分の落ちた落とし穴に何度も落ちる人のメモ帳

Javascript 自然数の約数の総和を求めたい

プログラム書く仕事が無いので、お脳が腐らないように息抜きにプログラムのパズルをしています。
自然数の約数の総和を求める方法を考えてたのでメモ。

数学的なやつ

自然数NP1a1P2a2素因数分解できる時
Nの約数の総和は

(1+P1+P1**2+...+P1**a1)(1+P2+P2**2+...+P2**a2)...

↓ 例

12 = 2**2 × 3
(1+2+2**2)(1+3) = 7*4 = 28

数学的な公式だと、素因数分解をするとエレガントに約数の総和が求められるのですが、素因数分解を行うプログラムが大変そうだったので別の方法を考えることにしました。

約数をループで探していく

  • N%C === 0 の時 Cは整数Nの約数
  • 1の次は2なので、N自身を除いた最大の約数は N/2 以下の数になる

と、上記の条件から作った関数がこちら

// n: int, n > 0
function divisorSum(n) {
  let c, r = n;
  if(n <= 0) return;
  c = Math.floor(n/2)+1;
  while(c--) {
    if(n%c === 0) r += c;
  }
  return r;
}

divisorSum(12) // => 28

 
N/2以下でループさせれば計算量が多少は少なくて済む気がします。(間違ってたらご指摘ください。数学苦手なので自信はありません。)
他にエレガントな方法や素因数分解するプログラムのヒントがあれば知りたいので教えてください!!
(素因数分解は脳内でどうやって素因数分解しているかを順序立ててトレースすれば良さそうな気もするけど、ループで約数探すより処理が多そうな気が…


[参考]

プログラマのための論理パズル 難題を突破する論理思考トレーニング

プログラマのための論理パズル 難題を突破する論理思考トレーニング