N が大きすぎると使えませんが、以下の二通りで求めてみました。 (ちなみに②の方が速い) ①素数の列を使わない方法 N = 10 ** 2 h = {1 => 1} ary = Array.new(N + 1, 1) ary[0], ary[1] = 0, 0 (2..N).each{|i| i.step(N, i){|d| if d == i s = ary[d] + 1 h.key?(s) ? h[s] += 1 : h[s] = 1 else ary[d] += 1 end } } p h 【コードの説明】 aryに約数(自身を含まない)の個数をいれていくことにする。 i (< n) が n の約数なら、ary[n] を 1 増やす。 i が n のときは ary はそのままで、h には結果を反映させることにする。 次のようにすればほんの少し速くなります。 N = 10 ** 7 h = {1 => 1} ary = Array.new(N + 1, 1) ary[0], ary[1] = 0, 0 (2..N / 2).each{|i| i.step(N, i){|d| if d == i s = ary[d] + 1 h.key?(s) ? h[s] += 1 : h[s] = 1 else ary[d] += 1 end } } (N / 2 + 1..N).each{|i| s = ary[i] + 1 h.key?(s) ? h[s] += 1 : h[s] = 1 } p h ②素数の列を使う方法 require 'prime' # dを素因数分解したときのiの次数 def d(d, i) s = 0 while d % i == 0 d /= i s += 1 end s end # @ary[j]を@hへ反映させる def h(j) s = @ary[j] @h.key?(s) ? @h[s] += 1 : @h[s] = 1 end N = 10 ** 7 @h = {1 => 1} @ary = Array.new(N + 1, 1) n = 2 Prime.each(N){|i| i.step(N, i){|d| @ary[d] *= d(d, i) + 1 } (n..i).each{|j| h(j)} n = i + 1 } (n..N).each{|j| h(j)} p @h