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