# the number to split into prime factors
PRODUCT=600_851_475_143



PRIME_MAX = Math.sqrt(PRODUCT).ceil
# There is not enough ram to sieve the primes, so use the CPU death method.

greatest_prime_factor = 0


def check_prime(x)
  (2..x/2).each{|n|
    return false if x%n == 0
  }
  return true
end

(2..PRIME_MAX).each{ |candidate|
  is_factor = PRODUCT%candidate == 0
  if is_factor
    # check primality
    is_prime = check_prime(candidate)
  end
  greatest_prime_factor = candidate if is_factor and is_prime
}

puts greatest_prime_factor