2

n の約数の個数を d(n) と表すことにする。
1から10までの整数に対し、
d(n) = 1 となるのは1個、
d(n) = 2 となるのは4個、
d(n) = 3 となるのは2個、
d(n) = 4 となるのは3個ある。

一般に、
1からNまでの整数に対し、「約数の数がs個になる」のはいくつあるか調べるには
どうすれば速く求まるでしょうか?

とりあえずなんの工夫もしていないコードをあげておきます。

require 'prime'

N = 10 ** 2
h = {}
(1..N).each{|i|
  s = 1
  i.prime_division.map{|j| s *= j[1] + 1}
  h.key?(s) ? h[s] += 1 : h[s] = 1
}
p h

出力結果
{1=>1, 2=>25, 3=>4, 4=>32, 6=>16, 5=>2, 8=>10, 9=>2, 10=>2, 12=>5, 7=>1}

1 件の回答 1

1

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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。