Skip to main content
4 / 5
コード修正。
TOM
  • 1,582
  • 1
  • 14
  • 37

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

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
}
(n..N).each{|j|
  s = ary[j]
  h.key?(s) ? h[s] += 1 : h[s] = 1
}
p h
TOM
  • 1,582
  • 1
  • 14
  • 37