Rubyで素因数を求める 〜Rubyでオイラープロジェクトを解こう！Problem3

Problem 3 - Project Eulerより

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
13195の素因数は、5、7、13および29である。
では600851475143の最大の素因数はいくらか。

素因数 - Wikipedia

素因数は自然数で、ある自然数の約数になる素数である。

最小の素数から対象の数を割って
割り切れる素数を順次見つけ出す

 def prime_factor(n)
   prime = 2
   result = []
   loop do
     break if n < prime
     while n.modulo(prime).zero?
       n = n / prime
       result << prime
     end
     prime = next_prime(prime)
   end
   result
 end

 def next_prime(prime)
   _next = prime + 1
   loop do
     return _next if prime?(_next)
     _next += 1
   end
 end

 def prime?(n)
   2.upto(n-1) do |i|
     return false if n.modulo(i).zero?
   end
   true
 end

primes = prime_factor(600851475143) # => [71, 839, 1471, 6857]
primes.last # => 6857