11259


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

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

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

[code]

    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
    
[/code]

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


CC BY-SA 3.0
2015-06-10T13:02:43.023
11225
2015-06-12T12:27:48.830
5363
question
ruby アルゴリズム
１からNまでの整数に対し、「約数の数がs個になる」のはいくつあるか調べるには？


N が大きすぎると使えませんが、以下の二通りで求めてみました。  
（ちなみに②の方が速い）

①素数の列を使わない方法

[code]

    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
    
[/code]

【コードの説明】  
aryに約数（自身を含まない）の個数をいれていくことにする。  
i (< n) が n の約数なら、ary[n] を 1 増やす。  
i が n のときは ary はそのままで、h には結果を反映させることにする。

次のようにすればほんの少し速くなります。

[code]

    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
    
[/code]

②素数の列を使う方法

[code]

    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
    
[/code]


CC BY-SA 3.0
2015-06-11T11:19:30.010
11259
2015-06-12T12:27:48.830
2015-06-12T12:27:48.830
5363
5363
11225
answer