Fun with largest prime factors

largest_prime_factor.rb

BIG_NUMBER = 600_851_475_143

require 'prime'
def slow_largest_prime_factor_of(n)
  possible_prime_factors = primes_up_to(Math.sqrt(n).to_i)
  returner = nil

  possible_prime_factors.each do |f|
    if n % f == 0
      returner = f
      break
    end
  end

  returner
end

# return a list of primes less than n, sorted in descending order
def primes_up_to(n)
  returner = []

  Prime.each(n) do |prime_number|
    returner.unshift prime_number
  end

  returner
end

require 'prime'
def largest_prime_factor_of(n)
  if n.prime?
    n
  else
    max = Math.sqrt(n).to_i # greatest possible factor is Math.sqrt(n)
    Prime.each(max) do |i|  # iterate over primes up to max
      if n % i == 0         # only care about factors
        factor = (n/i).to_i 
        other_factor = largest_prime_factor_of(factor)
        return [i, other_factor].max # recurse!
      end
    end
  end
end