





def        __lowercase       (				_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE = False     )			->       bool:


      '''simple docstring'''


      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_31_70_44_06_46_79_88_73_85_96_19_81 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
      SCREAMING_SNAKE_CASE		=						[
          20_47,
          1_37_36_53,
          25_32_60_01,
          32_15_03_17_51,
          2_15_23_02_89_87_47,
          3_47_47_49_66_03_83,
          3_41_55_00_71_72_83_21,
          1,
          3_82_51_23_05_65_46_41_30_51,
          1,
          1,
          31_86_65_85_78_34_03_11_51_16_74_61,
          3_31_70_44_06_46_79_88_73_85_96_19_81,
      ]

      SCREAMING_SNAKE_CASE		=						[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
                  SCREAMING_SNAKE_CASE		=						primes[:idx]
                  break
      SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						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:
            SCREAMING_SNAKE_CASE		=						False
            for r in range(_SCREAMING_SNAKE_CASE     ):
                  SCREAMING_SNAKE_CASE		=						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):
                        SCREAMING_SNAKE_CASE		=						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        __lowercase       (				)			->       None:


      '''simple docstring'''


      assert not miller_rabin(5_61     )
      assert miller_rabin(5_63     )
      # 2047

      assert not miller_rabin(83_82_01     )
      assert miller_rabin(83_82_07     )
      # 1_373_653

      assert not miller_rabin(17_31_60_01     )
      assert miller_rabin(17_31_60_17     )
      # 25_326_001

      assert not miller_rabin(30_78_38_66_41     )
      assert miller_rabin(30_78_38_66_53     )
      # 3_215_031_751

      assert not miller_rabin(1_71_30_45_57_48_01     )
      assert miller_rabin(1_71_30_45_57_48_19     )
      # 2_152_302_898_747

      assert not miller_rabin(2_77_97_99_72_83_07     )
      assert miller_rabin(2_77_97_99_72_83_27     )
      # 3_474_749_660_383

      assert not miller_rabin(1_13_85_00_23_90_94_41     )
      assert miller_rabin(1_13_85_00_23_90_95_27     )
      # 341_550_071_728_321

      assert not miller_rabin(1_27_50_41_01_88_48_80_43_51     )
      assert miller_rabin(1_27_50_41_01_88_48_80_43_91     )
      # 3_825_123_056_546_413_051

      assert not miller_rabin(7_96_66_46_44_58_50_77_87_79_18_67     )
      assert miller_rabin(7_96_66_46_44_58_50_77_87_79_19_51     )
      # 318_665_857_834_031_151_167_461

      assert not miller_rabin(55_28_40_67_74_46_64_78_97_66_03_33     )
      assert miller_rabin(55_28_40_67_74_46_64_78_97_66_03_59     )
      # 3_317_044_064_679_887_385_961_981
      # upper limit for probabilistic test


if __name__ == "__main__":
      test_miller_rabin()









from __future__ import annotations



def        __lowercase       (				_SCREAMING_SNAKE_CASE     )			->       list[int]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE		=						2
      SCREAMING_SNAKE_CASE		=						[]
      while i * i <= n:
            if n % i:
                  i += 1
            else:
                  n //= i
                  factors.append(_SCREAMING_SNAKE_CASE     )
      if n > 1:
            factors.append(_SCREAMING_SNAKE_CASE     )
      return factors


if __name__ == "__main__":
      import doctest

      doctest.testmod()


