【Ruby】200000以下の約数の合計を出力したい

Question

【やりたいこと】
Rubyで200000以下の約数の合計を出力したい。

200000の約数の合計ではなくて、200000以下の約数の合計です。

例：10の場合
１から１０までの約数は以下になるので、すべて合計して、87になる。
[[1], [1, 2], [1, 3], [1, 2, 4], [1, 5], [1, 2, 3, 6], [1, 7], [1, 2, 4, 8], [1, 3, 9], [1, 2, 5, 10]]

【なにが分からないか】
任意の値で結果を出力することができたが、200000など
大きい値だと処理が重くなり出力できない。

どうにかして出力したいが、方法が分からない

n = 200000
i = 1
result = []

while i <= n do
  result << (1..i).select{ |a|
    i % a == 0
   }
  i += 1
end

count = 0
(result.length).times{ |a|
  count += result[a].sum
}
puts count

Comments

[otn]

10の例で言いたいことはわかりますが、タイトルが間違っているので、直しておいた方がいいでしょうね。
× 200000以下の約数の合計を出力したい
○ 200000以下の数の約数の合計を出力したい

[melian]

Is there a formula to calculate the sum of all proper divisors of a number?
https://math.stackexchange.com/a/22723

Answer 1

Rubyには、標準ライブラリとしてprimeがあります（るりま）。

1からiまで連続して割り続けるより、遥かに高速に素因数分解ができます。

Comments

[winterboum]

素因数分解だと [1, 2, 4, 8] にならず [2, 2, 2] になってしまいますから、ひと工夫必要ですね

[maisumakun]

Prime.prime_divisionは2の4乗×3の2乗×7、というような情報を入れた配列が返ってきますので、約数の和は比較的出しやすいです。