# Path: mom/_compat.py
#   INT_MAX = sys.maxsize
#   INT_MAX = sys.maxint
# INT64_MAX = (1 << 63) - 1
# INT32_MAX = (1 << 31) - 1
# INT16_MAX = (1 << 15) - 1
# UINT128_MAX = (1 << 128) - 1    # 340282366920938463463374607431768211455L
# UINT64_MAX = 0xffffffffffffffff  # ((1 << 64) - 1)
# UINT32_MAX = 0xffffffff  # ((1 << 32) - 1)
# UINT16_MAX = 0xffff  # ((1 << 16) - 1)
# UINT8_MAX = 0xff
#   MACHINE_WORD_SIZE = 64
#   UINT_MAX = UINT64_MAX
#   MACHINE_WORD_SIZE = 32
#   UINT_MAX = UINT32_MAX
#   MACHINE_WORD_SIZE = 64
#   UINT_MAX = UINT64_MAX
#   LONG_TYPE = long
#   LONG_TYPE = int
#   INT_TYPE = long
#   INTEGER_TYPES = (int, long)
#   INT_TYPE = int
#   INTEGER_TYPES = (int,)
#   BYTES_TYPE = bytes
#   BYTES_TYPE = str
#   UNICODE_TYPE = unicode
#   BASESTRING_TYPE = basestring
#   HAVE_PYTHON3 = False
#   UNICODE_TYPE = str
#   BASESTRING_TYPE = (str, bytes)
#   HAVE_PYTHON3 = True
# ZERO_BYTE = byte_literal("\x00")
# EMPTY_BYTE = byte_literal("")
# EQUAL_BYTE = byte_literal("=")
# PLUS_BYTE = byte_literal("+")
# HYPHEN_BYTE = byte_literal("-")
# FORWARD_SLASH_BYTE = byte_literal("/")
# UNDERSCORE_BYTE = byte_literal("_")
# DIGIT_ZERO_BYTE = byte_literal("0")
# HAVE_LITTLE_ENDIAN = bool(struct.pack("h", 1) == "\x01\x00")
#   def byte_ord(byte_):
#   def byte_ord(byte_):
#   def byte_literal(literal):
#   def byte_literal(literal):
#   def dict_each(func, iterable):
#   def dict_each(func, iterable):
#   def next(iterator, default=throw):
#   def generate_random_bytes(count):
#     def generate_random_bytes(count):
#       def generate_random_bytes(count):
#       def generate_random_bytes(_):
# def get_word_alignment(num, force_arch=64,
#                        _machine_word_size=MACHINE_WORD_SIZE):
#   class Throw(object):


from mom import _compat
  import nump as np
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# http://goo.gl/9qEXu
# Public domain.

"""Generates a prime sieve."""

from __future__ import division


try:
  # TODO(yesudeep): numpy import disabled temporarily until we can convert
  # the generated list to Python native. Rename "nump" to "numpy" when ready.

  def make_prime_sieve(max_n):  # def _numpy_primesfrom2to(max_n):
    """Input n>=6, Returns a array of primes, 2 <= p < n"""
    sieve = np.ones(max_n // 3 + (max_n % 6 == 2), dtype=np.bool)
    sieve[0] = False
    for i in _compat.range(int(max_n ** 0.5) // 3 + 1):
      if sieve[i]:
        k = 3 * i + 1 | 1
        sieve[((k * k) // 3)::2 * k] = False
        sieve[(k * k + 4 * k - 2 * k * (i & 1)) // 3::2 * k] = False
    return np.r_[2, 3, ((3 * np.nonzero(sieve)[0] + 1) | 1)]

except ImportError:

  def make_prime_sieve(max_n):  # def _rwh_primes1(max_n):
    """Returns a list of primes < n"""
    sieve = [True] * (max_n // 2)

# Path: mom/_compat.py
#   INT_MAX = sys.maxsize
#   INT_MAX = sys.maxint
# INT64_MAX = (1 << 63) - 1
# INT32_MAX = (1 << 31) - 1
# INT16_MAX = (1 << 15) - 1
# UINT128_MAX = (1 << 128) - 1    # 340282366920938463463374607431768211455L
# UINT64_MAX = 0xffffffffffffffff  # ((1 << 64) - 1)
# UINT32_MAX = 0xffffffff  # ((1 << 32) - 1)
# UINT16_MAX = 0xffff  # ((1 << 16) - 1)
# UINT8_MAX = 0xff
#   MACHINE_WORD_SIZE = 64
#   UINT_MAX = UINT64_MAX
#   MACHINE_WORD_SIZE = 32
#   UINT_MAX = UINT32_MAX
#   MACHINE_WORD_SIZE = 64
#   UINT_MAX = UINT64_MAX
#   LONG_TYPE = long
#   LONG_TYPE = int
#   INT_TYPE = long
#   INTEGER_TYPES = (int, long)
#   INT_TYPE = int
#   INTEGER_TYPES = (int,)
#   BYTES_TYPE = bytes
#   BYTES_TYPE = str
#   UNICODE_TYPE = unicode
#   BASESTRING_TYPE = basestring
#   HAVE_PYTHON3 = False
#   UNICODE_TYPE = str
#   BASESTRING_TYPE = (str, bytes)
#   HAVE_PYTHON3 = True
# ZERO_BYTE = byte_literal("\x00")
# EMPTY_BYTE = byte_literal("")
# EQUAL_BYTE = byte_literal("=")
# PLUS_BYTE = byte_literal("+")
# HYPHEN_BYTE = byte_literal("-")
# FORWARD_SLASH_BYTE = byte_literal("/")
# UNDERSCORE_BYTE = byte_literal("_")
# DIGIT_ZERO_BYTE = byte_literal("0")
# HAVE_LITTLE_ENDIAN = bool(struct.pack("h", 1) == "\x01\x00")
#   def byte_ord(byte_):
#   def byte_ord(byte_):
#   def byte_literal(literal):
#   def byte_literal(literal):
#   def dict_each(func, iterable):
#   def dict_each(func, iterable):
#   def next(iterator, default=throw):
#   def generate_random_bytes(count):
#     def generate_random_bytes(count):
#       def generate_random_bytes(count):
#       def generate_random_bytes(_):
# def get_word_alignment(num, force_arch=64,
#                        _machine_word_size=MACHINE_WORD_SIZE):
#   class Throw(object):


# Path: mom/_prime_sieve.py
from mom import _compat
  import nump as np

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# http://goo.gl/9qEXu
# Public domain.

"""Generates a prime sieve."""

from __future__ import division


try:
  # TODO(yesudeep): numpy import disabled temporarily until we can convert
  # the generated list to Python native. Rename "nump" to "numpy" when ready.

  def make_prime_sieve(max_n):  # def _numpy_primesfrom2to(max_n):
    """Input n>=6, Returns a array of primes, 2 <= p < n"""
    sieve = np.ones(max_n // 3 + (max_n % 6 == 2), dtype=np.bool)
    sieve[0] = False
    for i in _compat.range(int(max_n ** 0.5) // 3 + 1):
      if sieve[i]:
        k = 3 * i + 1 | 1
        sieve[((k * k) // 3)::2 * k] = False
        sieve[(k * k + 4 * k - 2 * k * (i & 1)) // 3::2 * k] = False
    return np.r_[2, 3, ((3 * np.nonzero(sieve)[0] + 1) | 1)]

except ImportError:

  def make_prime_sieve(max_n):  # def _rwh_primes1(max_n):
    """Returns a list of primes < n"""
    sieve = [True] * (max_n // 2)

    for i in _compat.range(3, int(max_n ** 0.5) + 1, 2):