N が大きすぎると使えませんが、以下のように書き二通りで求めてみました。
(ちなみに②の方が速い)
①素数の列を使わない方法
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
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|
s = ary[j]
h.key?(s) ? h[s] += 1 : h[s] = 1
}
n = i + 1
}
p h