素因数分解

藤井四段の連勝記録、29連勝について、ある棋士が「28は完全数だったのに29になって残念だ」という趣旨の発言をしたそうだ。完全数とは自分自身を除く約数の和が自分自身と等しい数字だ。例えば6、1 + 2 + 3 = 6。(28は、1 + 2 + 4 + 7 + 14 = 28)
Rubyスクリプト完全数を計算する方法を考えているうちに素因数分解スクリプトができた。

num = 1234
print "#{num}\s=\s"

i = 0; j = 0; k = 0; cnt = 0
ary = [2]; hash = Hash.new
str = ""

i = 1
while i <= num - 2
  i += 2
  j = 0
  cnt = 0
  i.times{
    j += 1
    cnt += 1 if i % j == 0
    break if cnt > 2
  }
  ary.push(i) if cnt == 2
end

ary.each{|prime|
  k = 0
  while num % prime == 0
    k += 1
    num = num / prime
  end
  hash.store(prime, k) unless k == 0
}

hash.each{|key, val|
  str += "#{key}\^#{val}\s\*\s"
}

str.gsub!(/\^1/, "")
str.sub!(/\s\*\s$/, "")
print "#{str}\n"

実行すると、1234 = 2 * 617

  • -

require 'prime' でライブラリを読み込めば、1234.prime_division の一行ですみます。