def findFactors(num)#{{{
  num = num.to_f
  facs = []
  knockout = {}
  sqrt = Math.sqrt(num)
  1.upto sqrt.truncate do |n|
    next if !knockout[n].nil?
    qt = num / n
    if qt == qt.truncate
      facs.push n
      facs.push qt.to_i if n < qt
    elsif n != 1
      i = 0
      while i <= sqrt
        knockout[i] = true
        i += n
      end
    end
  end
  facs
end#}}}
def findFactorsSort(num)#{{{
  findFactors(num).sort
end#}}}

class Array
  def sum#{{{
    total = 0
    self.each do |item|
      total += item.to_i
    end
    total
  end#}}}
end

@memoizedprimes = []
def isPrime(num)#{{{
  return true if @memoizedprimes.include? num
  num = num.to_f
  2.upto Math.sqrt(num) do |n|
    qt = num / n
    if qt == qt.truncate
      return false
    end
  end
  @memoizedprimes.push num
  return true
end#}}}
def primesUpTo(num)#{{{
  primeslist = []
  0.upto num do |n|
    primeslist.push n
  end
  primeslist[0] = nil
  primeslist[1] = nil
  2.upto(num/2) do |n|
    next unless primeslist[n]
    limit = (num / n).floor
    2.upto limit do |nk|
      primeslist[nk*n] = nil
    end
  end
  primeslist
end#}}}

@memoizedfacs = {}
def factorial(n)#{{{
  if !@memoizedfacs[n].nil?
    return @memoizedfacs[n]
  elsif n == 0
    return 1
  else
    thisfac = n * factorial(n-1)
    @memoizedfacs[n] = thisfac
    return thisfac
  end
end#}}}