

"""simple docstring"""



def  _snake_case     (    UpperCAmelCase_  :					int					,   UpperCAmelCase_  :					bool = False			):
     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
     A__										=  [
         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,
     ]

     A__										=  [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
     for idx, _p in enumerate(UpperCAmelCase_					,   1			):
          if n < _p:
               # then we have our last prime to check
               A__										=  primes[:idx]
               break
     A__			,				A__										=  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__										=  False
          for r in range(UpperCAmelCase_			):
               A__										=  pow(UpperCAmelCase_					,   d * 2**r					,   UpperCAmelCase_			)
               # see article for analysis explanation for m
               if (r == 0 and m == 1) or ((m + 1) % n == 0):
                    A__										=  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     (    ):
     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"""



SCREAMING_SNAKE_CASE_					:	str							  =						'0.21.0'

from .accelerator import Accelerator
from .big_modeling import (
    cpu_offload,
    cpu_offload_with_hook,
    disk_offload,
    dispatch_model,
    init_empty_weights,
    init_on_device,
    load_checkpoint_and_dispatch,
)
from .data_loader import skip_first_batches
from .launchers import debug_launcher, notebook_launcher
from .state import PartialState
from .utils import (
    DeepSpeedPlugin,
    DistributedDataParallelKwargs,
    DistributedType,
    FullyShardedDataParallelPlugin,
    GradScalerKwargs,
    InitProcessGroupKwargs,
    find_executable_batch_size,
    infer_auto_device_map,
    is_rich_available,
    load_checkpoint_in_model,
    synchronize_rng_states,
)


if is_rich_available():
 from .utils import rich






