Problem 3

13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。

Problem 3 - PukiWiki

処理が重すぎて600851475143では途中で止まってしまう模様。当たり前だよねえ。

limit =13195
max = 0

(2..limit).each{|i|
  if limit%i == 0 then
    k = 0
    (2..(i/2).to_i).each{|j| k = 1 and break if i%j == 0 }
    max = i if k == 0
  end
}

p max

答え：29

それならば計算量を小さくしてみる。約数を見つける度に割って範囲を小さくする。

limit =600851475143
max = 2

(2..limit).each{|i|
  if limit%i == 0 then
    k = true
    (2..(i/2).to_i).each{|j| k=false and break if i%j == 0 }
    max = i and limit = (limit/i).to_i if k
    break if max >= limit
  end
}

p max

としたら一瞬ででました.

答え：6857