TONY0922のブログ

学んだことを適当に記録していくブログです。主にRubyで仕事してます。最近はJavaScriptとObjectibe-C始めました。Titanium関連もちょいちょい触ってます。更新頻度はそんなに高くないので、ご了承下さい。

ProjectEular Problem 3 「最大の素因数」

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203

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

class PrimeFactor
    def max_prime_factorized(num)
        i = 2
        factors = []
        while i < num
            if num % i == 0
                num = num / i
                factors << i
            else
                i += 1
            end
        end
        factors << num
        factors.max
    end
end

prime = PrimeFactor.new
print prime.max_prime_factorized(600851475143)
6857

再帰的なアルゴリズムにして、求める方法でも行けそう。