プログラム書く仕事が無いので、お脳が腐らないように息抜きにプログラムのパズルをしています。
自然数の約数の総和を求める方法を考えてたのでメモ。
数学的なやつ
自然数N
が P1
のa1乗、P2
のa2乗に素因数分解できる時
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
以下でループさせれば計算量が多少は少なくて済む気がします。(間違ってたらご指摘ください。数学苦手なので自信はありません。)
他にエレガントな方法や素因数分解するプログラムのヒントがあれば知りたいので教えてください!!
(素因数分解は脳内でどうやって素因数分解しているかを順序立ててトレースすれば良さそうな気もするけど、ループで約数探すより処理が多そうな気が…
[参考]

プログラマのための論理パズル 難題を突破する論理思考トレーニング
- 作者: Dennis E. Shasha,吉平健治
- 出版社/メーカー: オーム社
- 発売日: 2009/03/26
- メディア: 単行本
- 購入: 21人 クリック: 412回
- この商品を含むブログ (63件) を見る