





def   __snake_case    (       _lowerCAmelCase			:			int					,					_lowerCAmelCase			:			bool = 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 > 3317044064679887385961981 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
   A_       :					Union[str, Any]        =      [
       2047,
       1373653,
       25326001,
       3215031751,
       2152302898747,
       3474749660383,
       341550071728321,
       1,
       3825123056546413051,
       1,
       1,
       318665857834031151167461,
       3317044064679887385961981,
   ]

   A_       :					Union[str, Any]        =      [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
   for idx, _p in enumerate(_lowerCAmelCase					,					1						):
      if n < _p:
         # then we have our last prime to check
         A_       :					Dict        =      primes[:idx]
         break
   A_   ,    A_       :					Optional[Any]        =      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:
      A_       :					int        =      False
      for r in range(_lowerCAmelCase						):
         A_       :					int        =      pow(_lowerCAmelCase					,					d * 2**r					,					_lowerCAmelCase						)
         # see article for analysis explanation for m
         if (r == 0 and m == 1) or ((m + 1) % n == 0):
            A_       :					Tuple        =      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   __snake_case    (       )			->    None:
   assert not miller_rabin(561						)
   assert miller_rabin(563						)
   # 2047

   assert not miller_rabin(838201						)
   assert miller_rabin(838207						)
   # 1_373_653

   assert not miller_rabin(17316001						)
   assert miller_rabin(17316017						)
   # 25_326_001

   assert not miller_rabin(3078386641						)
   assert miller_rabin(3078386653						)
   # 3_215_031_751

   assert not miller_rabin(1713045574801						)
   assert miller_rabin(1713045574819						)
   # 2_152_302_898_747

   assert not miller_rabin(2779799728307						)
   assert miller_rabin(2779799728327						)
   # 3_474_749_660_383

   assert not miller_rabin(113850023909441						)
   assert miller_rabin(113850023909527						)
   # 341_550_071_728_321

   assert not miller_rabin(1275041018848804351						)
   assert miller_rabin(1275041018848804391						)
   # 3_825_123_056_546_413_051

   assert not miller_rabin(79666464458507787791867						)
   assert miller_rabin(79666464458507787791951						)
   # 318_665_857_834_031_151_167_461

   assert not miller_rabin(552840677446647897660333						)
   assert miller_rabin(552840677446647897660359						)
   # 3_317_044_064_679_887_385_961_981
   # upper limit for probabilistic test


if __name__ == "__main__":
 test_miller_rabin()







from __future__ import annotations

from cmath import sqrt

def   __snake_case    (       _lowerCAmelCase			:			int					,					_lowerCAmelCase			:			int					,					_lowerCAmelCase			:			int						)			->    tuple[complex, complex]:

   if a == 0:
      raise ValueError("Coefficient 'a' must not be zero."						)
   A_       :					Tuple        =      b * b - 4 * a * c

   A_       :					Any        =      (-b + sqrt(_lowerCAmelCase						)) / (2 * a)
   A_       :					Union[str, Any]        =      (-b - sqrt(_lowerCAmelCase						)) / (2 * a)

   return (
       root_a.real if not root_a.imag else root_a,
       root_a.real if not root_a.imag else root_a,
   )

def   __snake_case    (       )			->    List[Any]:
   A_   ,    A_       :					Optional[Any]        =      quadratic_roots(a=5					,					b=6					,					c=1						)
   print(f"The solutions are: {solutiona} and {solutiona}"						)


if __name__ == "__main__":
 main()
