$primes_cache = []

def get_next_prime(index)
  if index <= $primes_cache.length
    #get from cache
    return $primes_cache[index-1]
  else
    #calculate new prime
    if not $primes_cache[-1]
      number = 2
    else
      number = $primes_cache[-1] + 1
    end
    while true
      is_prime = true
      $primes_cache.each do |prime|
        if number % prime == 0
          is_prime = false
          break
        end
      end # primes_cache.each
      if is_prime
        break
      else
        number += 1
      end
    end # while
    $primes_cache.push(number)
  end # else
  number
end

def get_prime_by_index(index)
  if index < 1
    return nil
  end

  prime = nil
  cache_length = $primes_cache.length
  if index <= cache_length
    #get from cache
    return $primes_cache[index-1]
  else
    while cache_length < index
      cache_length += 1
      prime = get_next_prime(cache_length)
    end
  end
  prime
end

def divisors_prime(number)
  div_array = [1]
  # number factorization
  #factor_array = []
  index = 1
  while number > 1
    prime = get_prime_by_index(index)
    mul_pos = 0
    while number % prime == 0
      number /= prime
      #factor_array.push(prime)
      # push real divisors
      temp_array = []
      mul_pos.upto(div_array.length-1) { |i| temp_array.push(div_array[i] * prime) }
      mul_pos += div_array.length
      div_array.concat(temp_array)
    end
    index += 1
  end
  div_array
end

def divisors(number)
  div_array = []
  x = 1
  while x <= Integer(Math.sqrt(number))
    if number % x == 0
      if x == Integer(number/x)
        div_array.push(x)
      else
        div_array.push(x, number/x)
      end
    end
    x += 1
  end
  div_array
end

def calculate_start(max_sum)
  sum = 0
  x = 1
  while sum < max_sum
    sum += x
    x += 1
  end
  x - 1
end

def main
  input = 29000000
  #input = 50000 # result - 3747
  #input = 70
  div_sum = input / 10
  start = 1
  #start = div_sum - 1
  #start = calculate_start(div_sum) * 2
  while true
    sum = divisors(start).inject { |sum, x| sum + x }
    if start % 10000 == 0
      print "Processing #{start} of #{div_sum-1}\n"
      puts "Sum #{sum}"
    end
    #if divisors(start).inject { |sum, x| sum + x } == div_sum
    if sum >= div_sum
      break
    elsif start >= div_sum - 1
      print "Can't find such number\n"
      break
    end
    start += 1
  end
  start
end

#load prime numbers from file
File.open('primes.txt') do |fin|
  fin.each_line { |line| $primes_cache.push(line.to_i) }
end

# UNCOMMENT NEXT LINE TO SOLVE PROBLEM
#print main

# UNCOMMENT NEXT LINE TO NOT RUN TESTS
#__END__

# test section

counter_p = 0
counter_s = 0
time_p = 0
time_s = 0
numbers = (100_000..1_000_000)
numbers.each do |number|
  start_time = Time.now
  divisors_prime(number)
  end_time = Time.now
  div_prime_time = end_time - start_time
  time_p += div_prime_time

  start_time = Time.now
  divisors(number)
  end_time = Time.now
  div_time = end_time - start_time
  time_s += div_time

  if div_prime_time > div_time
    puts "Number: #{number}, prime: #{div_prime_time}, simple: #{div_time}"
    counter_p += 1
  elsif div_prime_time < div_time
    counter_s += 1
  end
end
puts "Divisors prime losses:  #{counter_p}, time: #{time_p}"
puts "Divisors simple losses: #{counter_s}, time: #{time_s}"