




'''simple docstring'''






def 		UpperCamelCase__      (		__SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE = False		)    ->   bool:
      if n == 2:
            return True
      if not n % 2 or n < 2:
            return False
      if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
            return False
      if n > 3_3170_4406_4679_8873_8596_1981 and not allow_probable:
            raise ValueError(
                'Warning: upper bound of deterministic test is exceeded. '
                'Pass allow_probable=True to allow probabilistic test. '
                'A return value of True indicates a probable prime.'		)
      # array bounds provided by analysis
      snake_case__       :   Any	      =    [
          2047,
          137_3653,
          2532_6001,
          32_1503_1751,
          2_1523_0289_8747,
          3_4747_4966_0383,
          341_5500_7172_8321,
          1,
          382_5123_0565_4641_3051,
          1,
          1,
          3186_6585_7834_0311_5116_7461,
          3_3170_4406_4679_8873_8596_1981,
      ]

      snake_case__       :   List[str]	      =    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
      for idx, _p in enumerate(__SCREAMING_SNAKE_CASE				,      1		):
            if n < _p:
                  # then we have our last prime to check
                  snake_case__       :   Any	      =    primes[:idx]
                  break
      snake_case__      ,							snake_case__       :   Optional[int]	      =    n - 1, 0
      # break up n -1 into a power of 2 (s) and
      # remaining odd component
      # essentially, solve for d * 2 ** s == n - 1
      while d % 2 == 0:
            d //= 2
            s += 1
      for prime in plist:
            snake_case__       :   str	      =    False
            for r in range(__SCREAMING_SNAKE_CASE		):
                  snake_case__       :   List[Any]	      =    pow(__SCREAMING_SNAKE_CASE				,      d * 2**r				,      __SCREAMING_SNAKE_CASE		)
                  # see article for analysis explanation for m
                  if (r == 0 and m == 1) or ((m + 1) % n == 0):
                        snake_case__       :   Any	      =    True
                        # this loop will not determine compositeness
                        break
            if pr:
                  continue
            # if pr is False, then the above loop never evaluated to true,
            # and the n MUST be composite
            return False
      return True






def 		UpperCamelCase__      (		)    ->   None:
      assert not miller_rabin(561		)
      assert miller_rabin(563		)
      # 2047

      assert not miller_rabin(83_8201		)
      assert miller_rabin(83_8207		)
      # 1_373_653

      assert not miller_rabin(1731_6001		)
      assert miller_rabin(1731_6017		)
      # 25_326_001

      assert not miller_rabin(30_7838_6641		)
      assert miller_rabin(30_7838_6653		)
      # 3_215_031_751

      assert not miller_rabin(1_7130_4557_4801		)
      assert miller_rabin(1_7130_4557_4819		)
      # 2_152_302_898_747

      assert not miller_rabin(2_7797_9972_8307		)
      assert miller_rabin(2_7797_9972_8327		)
      # 3_474_749_660_383

      assert not miller_rabin(113_8500_2390_9441		)
      assert miller_rabin(113_8500_2390_9527		)
      # 341_550_071_728_321

      assert not miller_rabin(127_5041_0188_4880_4351		)
      assert miller_rabin(127_5041_0188_4880_4391		)
      # 3_825_123_056_546_413_051

      assert not miller_rabin(796_6646_4458_5077_8779_1867		)
      assert miller_rabin(796_6646_4458_5077_8779_1951		)
      # 318_665_857_834_031_151_167_461

      assert not miller_rabin(5528_4067_7446_6478_9766_0333		)
      assert miller_rabin(5528_4067_7446_6478_9766_0359		)
      # 3_317_044_064_679_887_385_961_981
      # upper limit for probabilistic test


if __name__ == "__main__":
      test_miller_rabin()






'''simple docstring'''






# This code is adapted from OpenAI's release
# https://github.com/openai/human-eval/blob/master/human_eval/execution.py

import contextlib
import faulthandler
import io
import multiprocessing
import os
import platform
import signal
import tempfile






def 		UpperCamelCase__      (		__SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE		)    ->   Dict:
      snake_case__       :   int	      =    multiprocessing.Manager()
      snake_case__       :   Any	      =    manager.list()

      snake_case__       :   List[str]	      =    multiprocessing.Process(target=__SCREAMING_SNAKE_CASE				,      args=(check_program, result, timeout)		)
      p.start()
      p.join(timeout=timeout + 1		)
      if p.is_alive():
            p.kill()

      if not result:
            result.append('timed out'		)

      return {
          "task_id": task_id,
          "passed": result[0] == "passed",
          "result": result[0],
          "completion_id": completion_id,
      }






def 		UpperCamelCase__      (		__SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE		)    ->   Tuple:
      with create_tempdir():
            # These system calls are needed when cleaning up tempdir.
            import os
            import shutil

            snake_case__       :   List[Any]	      =    shutil.rmtree
            snake_case__       :   Tuple	      =    os.rmdir
            snake_case__       :   Any	      =    os.chdir

            # Disable functionalities that can make destructive changes to the test.
            reliability_guard()

            # Run program.
            try:
                  snake_case__       :   Union[str, Any]	      =    {}
                  with swallow_io():
                        with time_limit(__SCREAMING_SNAKE_CASE		):
                              exec(__SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE		)
                  result.append('passed'		)
            except TimeoutException:
                  result.append('timed out'		)
            except BaseException as e:
                  result.append(f"failed: {e}"		)

            # Needed for cleaning up.
            snake_case__       :   List[Any]	      =    rmtree
            snake_case__       :   Optional[int]	      =    rmdir
            snake_case__       :   Dict	      =    chdir






@contextlib.contextmanager
def 		UpperCamelCase__      (		__SCREAMING_SNAKE_CASE		)    ->   List[str]:
      def signal_handler(__SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE		):
            raise TimeoutException('Timed out!'		)

      signal.setitimer(signal.ITIMER_REAL				,      __SCREAMING_SNAKE_CASE		)
      signal.signal(signal.SIGALRM				,      __SCREAMING_SNAKE_CASE		)
      try:
            yield
      finally:
            signal.setitimer(signal.ITIMER_REAL				,      0		)






@contextlib.contextmanager
def 		UpperCamelCase__      (		)    ->   List[str]:
      snake_case__       :   Dict	      =    WriteOnlyStringIO()
      with contextlib.redirect_stdout(__SCREAMING_SNAKE_CASE		):
            with contextlib.redirect_stderr(__SCREAMING_SNAKE_CASE		):
                  with redirect_stdin(__SCREAMING_SNAKE_CASE		):
                        yield






@contextlib.contextmanager
def 		UpperCamelCase__      (		)    ->   Optional[int]:
      with tempfile.TemporaryDirectory() as dirname:
            with chdir(__SCREAMING_SNAKE_CASE		):
                  yield dirname






class        lowercase_      (						lowerCAmelCase_							):
     pass






class        lowercase_      (						io.StringIO							):





     def 			_lowerCAmelCase      (     self     :					Optional[Any]     ,							*__lowerCamelCase     :					int     ,							**__lowerCamelCase     :					Optional[int]			):
           raise OSError





     def 			_lowerCAmelCase      (     self     :					int     ,							*__lowerCamelCase     :					List[Any]     ,							**__lowerCamelCase     :					Tuple			):
           raise OSError





     def 			_lowerCAmelCase      (     self     :					Any     ,							*__lowerCamelCase     :					int     ,							**__lowerCamelCase     :					Union[str, Any]			):
           raise OSError





     def 			_lowerCAmelCase      (     self     :					Tuple     ,							*__lowerCamelCase     :					List[str]     ,							**__lowerCamelCase     :					Optional[Any]			):
           return False






class        lowercase_      (						contextlib._RedirectStream							):  # type: ignore
     A_											=			"stdin"






@contextlib.contextmanager
def 		UpperCamelCase__      (		__SCREAMING_SNAKE_CASE		)    ->   List[str]:
      if root == ".":
            yield
            return
      snake_case__       :   str	      =    os.getcwd()
      os.chdir(__SCREAMING_SNAKE_CASE		)
      try:
            yield
      except BaseException as exc:
            raise exc
      finally:
            os.chdir(__SCREAMING_SNAKE_CASE		)






def 		UpperCamelCase__      (		__SCREAMING_SNAKE_CASE=None		)    ->   Any:

      if maximum_memory_bytes is not None:
            import resource

            resource.setrlimit(resource.RLIMIT_AS				,      (maximum_memory_bytes, maximum_memory_bytes)		)
            resource.setrlimit(resource.RLIMIT_DATA				,      (maximum_memory_bytes, maximum_memory_bytes)		)
            if not platform.uname().system == "Darwin":
                  resource.setrlimit(resource.RLIMIT_STACK				,      (maximum_memory_bytes, maximum_memory_bytes)		)

      faulthandler.disable()

      import builtins

      snake_case__       :   List[Any]	      =    None
      snake_case__       :   List[str]	      =    None

      import os

      snake_case__       :   List[Any]	      =    '1'

      snake_case__       :   Union[str, Any]	      =    None
      snake_case__       :   Tuple	      =    None
      snake_case__       :   Dict	      =    None
      snake_case__       :   Tuple	      =    None
      snake_case__       :   List[str]	      =    None
      snake_case__       :   Any	      =    None
      snake_case__       :   Optional[Any]	      =    None
      snake_case__       :   Union[str, Any]	      =    None
      snake_case__       :   int	      =    None
      snake_case__       :   Optional[int]	      =    None
      snake_case__       :   Union[str, Any]	      =    None
      snake_case__       :   List[Any]	      =    None
      snake_case__       :   Optional[int]	      =    None
      snake_case__       :   Union[str, Any]	      =    None
      snake_case__       :   Tuple	      =    None
      snake_case__       :   int	      =    None
      snake_case__       :   Optional[Any]	      =    None
      snake_case__       :   Optional[int]	      =    None
      snake_case__       :   List[str]	      =    None
      snake_case__       :   List[str]	      =    None
      snake_case__       :   List[str]	      =    None
      snake_case__       :   Dict	      =    None
      snake_case__       :   Optional[Any]	      =    None
      snake_case__       :   List[Any]	      =    None
      snake_case__       :   Tuple	      =    None
      snake_case__       :   Optional[int]	      =    None
      snake_case__       :   int	      =    None

      import shutil

      snake_case__       :   List[str]	      =    None
      snake_case__       :   List[Any]	      =    None
      snake_case__       :   List[Any]	      =    None

      import subprocess

      snake_case__       :   int	      =    None  # type: ignore

      snake_case__       :   Dict	      =    None

      import sys

      snake_case__       :   Tuple	      =    None
      snake_case__       :   Tuple	      =    None
      snake_case__       :   List[str]	      =    None
      snake_case__       :   Optional[int]	      =    None
      snake_case__       :   List[Any]	      =    None
