【Ruby】約数を全て求めたい話 #Ruby

概要

現在、与えられた数の約数を全て求めたい状況にあるのですが、まずパっと思いつくものとして、2からその数の半分までの数で一つ一つその数自身を割っていき余りが０だったら約数、みたいな方法があります。

でもそれだと素数の場合や、「213」(=71☓3)などの素因数分解したとき素因数の個数が少ない数字の場合、その数の半分までいちいち割り切れるかを確かめるのが頭悪い感じがします。

今回は何かいい感じに書けないだろうかと試行錯誤した内の案外よかった案を紹介します。

こんな感じ

後で別のメソッドと比較するため、メソッド名を my_divisor_list とします。

require 'prime'

class Integer
  def my_divisor_list
    divisors = [1]
    primes = []
    Prime.prime_division(self).each do |prime|
      prime[1].times {primes << prime[0]}
    end

    1.upto(primes.size) do |i|
      primes.combination(i) do |prime|
        divisors << prime.inject{|a,b| a *= b}
      end
    end

    divisors.uniq!
    divisors.sort!
    return divisors
  rescue ZeroDivisionError
    return
  end
end

処理の流れ

素因数分解して、素因数の配列を得ます。
その配列からi個の要素を選んだ時、順序を考慮せず重複しない組合せを作り、その組合せの要素を全て乗算した結果を最終的に返す配列に入れていきます。（iは1から配列の要素数まで繰り返します）
この時点で最終的に返す配列の要素に重複がある場合があるので重複をなくします。
最後は昇順にソートして配列を返します。

結果

今回は 自然数 に対して 正の約数 を返すことを考えます。

全ての整数は0の約数なのですが、0に使うと Prime.prime_division(self) でエラーとなるのでそれをキャッチしてとりあえずnilを返しています。なお、負の整数に使うと負の約数と正の約数を返します。

こんな感じでちゃんと全ての約数が求められています。

p 13.my_divisor_list # => [1, 13]
p 50.my_divisor_list # => [1, 2, 5, 10, 25, 50]

愚直メソッドとの比較

与えられた整数の約数を全て求めるメソッドができましたが、果たしてこれはいい感じになっているのかどうか。愚直に余りが0であるかを見ていく方法と簡単に比較してみます。

# coding: utf-8
require 'prime'
require 'benchmark'

class Integer
  def my_divisor_list
    # (省略)
  end

  def divisor_list
    devisors = [1]
    2.upto(self/2) do |i|
      devisors << i if self%i == 0
    end
    devisors << self
    return devisors
  end
end

def time_compare(num)
  puts "\n#{num}の比較結果"
  result = Benchmark.realtime do
    num.my_divisor_list
  end
  puts "my_divisor_list 実行時間 #{result} s"

  result = Benchmark.realtime do
    num.divisor_list
  end
  puts "   divisor_list 実行時間 #{result} s"
end

先ほど紹介した方のメソッドを my_divisor_list とし、比較する愚直メソッドをdivisor_list とします。そして、与えられた数に対してそれぞれのメソッドを実行し、実行時間を表示する簡易的なメソッドを作ります。

結果

time_compare(10)
time_compare(100)
time_compare(1000)
time_compare(10000)
time_compare(100000)
time_compare(1000000)
time_compare(10000000)

↓

実行結果

10の比較結果
my_divisor_list 実行時間 4.6551e-05 s
   divisor_list 実行時間 3.962e-06 s

100の比較結果
my_divisor_list 実行時間 0.001296356 s
   divisor_list 実行時間 1.1698e-05 s

1000の比較結果
my_divisor_list 実行時間 7.2019e-05 s
   divisor_list 実行時間 4.5648e-05 s

10000の比較結果
my_divisor_list 実行時間 0.000259539 s
   divisor_list 実行時間 0.000409748 s

100000の比較結果
my_divisor_list 実行時間 0.001171235 s
   divisor_list 実行時間 0.00404551 s

1000000の比較結果
my_divisor_list 実行時間 0.007555651 s
   divisor_list 実行時間 0.049820061 s

10000000の比較結果
my_divisor_list 実行時間 0.022002619 s
   divisor_list 実行時間 0.431983437 s

我ながらなんて雑な比較方法なんだ…orz
大体５桁以上から愚直なやつに勝てるようになるみたいですね。

また、同じ桁数であっても素数や素因数分解したときの素因数の個数が少ない数の場合、もっと違いがでてきます。

time_compare(100000)
time_compare(100313) # 素数

↓

実行結果

100000の比較結果
my_divisor_list 実行時間 0.00132452 s
   divisor_list 実行時間 0.003932038 s

100313の比較結果
my_divisor_list 実行時間 0.000107305 s
   divisor_list 実行時間 0.003936902 s

まとめ

改善点

今回の方法、先程も述べた通り素数などに対しては速いのですが、それ以外の場合ではいろいろ余分な処理もしてしまっています。例えば「60」を素因数分解すると[2,2,3,5]となり2がふたつ出てきます。そうなるとそこから３つの要素を取り出して順序を考慮しない組合せをつくる場合、[2,3,5]がふたつ出てきてしまうので最後に重複を取り除いています。ここを重複なく取り出せればいいのですが、その処理をした方が速くなるのか放っといた方がいいのか正直わかりません。

とりあえず、この方法でやってみて重大な欠点等見つかったらまた修正していくかもしれません。

補足

愚直な方法、その数の半分まで調べなくても実は√nまで調べて残りはそこまでで得た約数でnを割っていけば全ての約数を求めることができるのでもうちょっと速くなると思います。

追記(2014/12/03)

コメントで提案していただいたメソッドの方が速かったので自分のものと比較して見ていきます。

例えば60の約数を考える場合、まず自分のメソッドでは因数分解をして [2, 2, 3, 5] という配列を得ます。そこからこの配列に対してべき集合をとって、空集合を除く各要素(配列)に inject(&:*) して約数を得ていました。

[2]
[2]
[3]
[5]
[2, 2]
[2, 3]
[2, 5]
[2, 3]
[2, 5]
[3, 5]
[2, 2, 3]
[2, 2, 5]
[2, 3, 5]
[2, 3, 5]
[2, 2, 3, 5]

しかしこの方法では因数分解して求めた配列の要素に重複があると、上の図のように組合せに重複がでてきてしまい、この分余計に計算をしてしまっているのです。

一方提案していただいたメソッドではどうなるかというと、

require 'prime'

class Integer
  def my_divisor_list2
    return [1] if self == 1
    Prime.prime_division(self).map do |e|
      Array.new(e[1]+1).map.with_index do |element, i|
        e[0]**i
      end
    end.inject{|p,q| p.product(q)}.map do |a|
      [a].flatten.inject(&:*)
    end.sort
  end
end

因数分解した結果を [[1, 2, 4], [1, 3], [1, 5]] という配列にします。これなら確かに同じ数が現れることは無いですね。なので配列同士の要素の組合せも重複しません。

[1, 1, 1]
[1, 1, 5]
[1, 3, 1]
[1, 3, 5]
[2, 1, 1]
[2, 1, 5]
[2, 3, 1]
[2, 3, 5]
[4, 1, 1]
[4, 1, 5]
[4, 3, 1]
[4, 3, 5]

これらの配列の各要素の積がそのまま約数になっています。
とてもスッキリしていていい感じです。

【Ruby】 約数を全て求めたい話

概要

こんな感じ

処理の流れ

結果

愚直メソッドとの比較

結果

まとめ

改善点

補足

追記(2014/12/03)

【Ruby】約数を全て求めたい話