Class Prime::EratosthenesSieve < Object

# File ../ruby/lib/prime.rb, line 441
def next_to(n)
  n = (n-1).div(2)*2+3 # the next odd number to given n
  table_index, integer_index, bit_index = indices(n)
  loop do
    extend_table until @tables.length > table_index
    for j in integer_index...ENTRIES_PER_TABLE
      if !@tables[table_index][j].zero?
        for k in bit_index...BITS_PER_ENTRY
          return NUMS_PER_TABLE*table_index + NUMS_PER_ENTRY*j + 2*k+1 if !@tables[table_index][j][k].zero?
        end
      end
      bit_index = 0
    end
    table_index += 1; integer_index = 0
  end
end

# File ../ruby/lib/prime.rb, line 471
def extend_table
  lbound = NUMS_PER_TABLE * @tables.length
  ubound = lbound + NUMS_PER_TABLE
  new_table = [FILLED_ENTRY] * ENTRIES_PER_TABLE # which represents primarity in lbound...ubound
  (3..Integer(Math.sqrt(ubound))).step(2) do |p|
    i, j, k = indices(p)
    next if @tables[i][j][k].zero?

    start = (lbound.div(p)+1)*p  # least multiple of p which is >= lbound
    start += p if start.even?
    (start...ubound).step(2*p) do |n|
      _, j, k = indices(n)
      new_table[j] &= FILLED_ENTRY^(1<<k)
    end
  end
  @tables << new_table.freeze
end

# File ../ruby/lib/prime.rb, line 460
def indices(n)
  #   binary digits of n: |0|1|2|3|4|5|6|7|8|9|10|11|....
  #   indices:            |-|    k  |  j  |     i
  # because of NUMS_PER_ENTRY, NUMS_PER_TABLE

  k = (n & 0b00011111) >> 1
  j = (n & 0b11100000) >> 5
  i = n >> 8
  return i, j, k
end