Google Code Jam練習

Google Code Jamの練習問題に久しぶりにチャレンジ

問題

連続する複数の整数を、以下の手順によっていくつかの集合に分割します。

まず、対象となる整数の区間と、ある整数 P が与えられます。 初期状態では、区間中の整数はそれぞれその整数のみを含む別々の集合に属しています。 そして、区間に属する整数同士のペアのそれぞれについて、その 2 つの整数に共通する P 以上の素因数が存在するならば、その 2 つの整数が属する集合同士を併合して 1 つの集合にする、という操作を行います。

この手順を終えたとき、集合の数はいくつになっているでしょうか?

http://code.google.com/codejam/contest/1343486/dashboard#s=p1


今回はRubyで。
下はその恥ずかしいコード。


考えたのは、とりあえず区間の数を素因数分解して区間の数の配列の代わりにその素因数の配列の配列
を作って、その二次元配列を走査して一致する数があったら消しながら集合の数を減らしていくという方法。
(消しながらなのは、走査の過程で一度チェックした数がまた出たときにまた同じ数を走査してしまうから)

class Calc
  def decomposit_prime( n, d )
    a = 2
    b = []

    while n >= a * a
      if n % a == 0
        if(a >= d)
          b << a
        end
        n /= a
      else
        a += 1
      end
    end
    
    if(n >= d)
      b << n
    end
    return b
  end
end

tmp = []
open("text.txt") do |file|
  file.each do |s|
    tmp << s.split(nil)
  end
end

tmp.flatten
n = tmp.slice!(0.1)
n = n.shift

n.to_i.times do

  a = tmp.slice!(0.1)
  b = a.slice(0.1)
  c = a.slice(1.2)
  d = a.slice(2.3)
  e = c.to_i - b.to_i
  f = []

  for i in b.to_i..c.to_i - 1 do
    b = b.to_i + 1
    obj_calc = Calc.new
    f << obj_calc.decomposit_prime(b, d.to_i)
  end

  g = f.size
  g.times do |h|
    i = f[h].size
    i.times do |j|
       k = f.size - 1
       cnt = 0
       k.times do |l|
         if(l + 1 <= f.size)
           if(f[l + 1].nil?) then
           else
             m = f[l+1].size
             m.times do |n|
               if(f[h][j] == f[l+1][n])
                 if[l+1][n].nil? then
                 else
                   cnt = cnt + 1
                   if(cnt == 2)
                     e = e - 1
                     f.delete(f[l+1][n])
                     f[h].delete(f[l+1][n])
                    end
                 end
               end
             end
           end
         end
       end
    end
  end
  puts "Case #: #{e}"
end