factorial

def product(arr)
    def rec_product(n, step, arr)
        return arr[n] if step > n
        newstep = step << 1
        t = rec_product(n, newstep, arr) *
            rec_product(n-step, newstep, arr)
        return t
    end
    rec_product(arr.length-1, 1, arr)
end

SMALL_ODD_SWING = [ 1,1,1,3,3,15,5,35,35,315,63,693,231,3003,429,6435,6435,109395,
                  12155,230945,46189,969969,88179,2028117,676039,16900975,1300075,
                  35102025,5014575,145422675,9694845,300540195,300540195 ]

PRECOMPUTED_ODD_SWINGS_NUM = SMALL_ODD_SWING.length

require 'prime'
PRIMES = Prime.each(1_000_000).to_a

def lower_bound(arr, n)
  l = 0
  r = arr.length
  while r > l
    m = (l + r) / 2
    if arr[m] < n
      l = m + 1
    else
      r = m
    end
  end
  l
end

class Integer
  def primes_upto(n)
    b = lower_bound(PRIMES, self)
    e = lower_bound(PRIMES, n + 1)
    PRIMES[b ... e]
  end
end

def odd_swing(n)
    return SMALL_ODD_SWING[n] if n < PRECOMPUTED_ODD_SWINGS_NUM
    root_n = (Math.sqrt n).floor
    prime_list = []
    a_primes = 3.primes_upto(root_n)
    b_primes = (root_n+1).primes_upto(n / 3)
    a_primes.each do |prime|
        q, p = n, 1
        while true do
            q /= prime
            break if q == 0
            p *= prime if q & 1 == 1
        end
        prime_list << p if p > 1
    end
    b_primes.each do |prime|
        prime_list << prime if (n / prime) & 1 == 1
    end
    product(prime_list) * product(((n/2)+1).primes_upto(n))
end

class FactorialCalculator
  def calc(n)
      @swings = []
      @counter = 0
      shift = 0
      t = n
      while t > 0 do
          if t >= PRECOMPUTED_ODD_SWINGS_NUM
              @swings << odd_swing(t)
              @counter += 1
          end
          t /= 2
          shift += t
      end
      return rec_factorial(n) << shift
  end

  private
  def rec_factorial(n)
      return 1 if n < 2
      t = rec_factorial(n/2)
      t *= t
      if n < PRECOMPUTED_ODD_SWINGS_NUM
          return t * SMALL_ODD_SWING[n]
      else
          @counter -= 1
          return t * @swings[@counter]
      end
  end
end

puts FactorialCalculator.new.calc(1_000_000).to_s(16)