AtCoder Beginner Contest 142「D - Disjoint Set of Common Divisors」（Ruby）

Rubyって標準添付ライブラリで素因数分解できるんですね

問題

D - Disjoint Set of Common Divisors

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文 正整数 A , B が与えられます。

A と B の正の公約数の中からいくつかを選びます。

ただし、選んだ整数の中のどの異なる 2 つの整数についても互いに素でなければなりません。

最大でいくつ選べるでしょうか。

考えたこと

まずAとBの公約数を求める必要があります。

調べたところ、Rubyには標準添付ライブラリに素因数分解の処理が用意されています。

require 'prime'
12.prime_division
#=> [[2, 2], [3, 1]]
#２の２乗、３の１乗

18.prime_division
#=> [[2, 1], [3, 2]]
#２の１乗、３の２乗

このように、配列で素因数分解された結果が出力できるので、これで公約数を求めることが出来ます。

あとは二つの数字の素因数分解した結果を見比べて、一致する数を集計するだけです。

なお、今回は「互いに素」ということなので、各配列の先頭部分の素数だけ見れば良いです。

提出コード

思いつくままに書いたので汚い・・・

require 'prime'
 
a,b = gets.split.map(&:to_i)
 
a_f = a.prime_division
b_f = b.prime_division
 
arr = []
delete_f = true
a_f.each do |aa|
  while delete_f do
    b_f.delete_if do |bb|
      if aa[0] == bb[0]
        arr << aa[0]
        delete_f = false
        true
      elsif aa[0] < bb[0]
        false
      else
        true
      end
    end
    delete_f = false
  end
  delete_f = true
end
 
puts arr.size + 1

補足

素因数分解には、Linuxコマンドのfactorコマンドを使用する方法もあります。

RubyでLinuxコマンドを呼び出す場合は、バッククォート（｀）で括れば良いです

x = 12
`factor #{x}`
#=> "12: 2 2 3\n"

これを使って、もっとシンプルにしたコードがこちらです。

a, b = gets.split.map(&:to_i)
g = a.gcd(b)
s = `factor #{g}`.split[1..-1].map(&:to_i)
p s.uniq.size+1