

"""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"""



def  _snake_case     (    UpperCAmelCase_  :					int			):
     A__										=  generate_pascal_triangle(UpperCAmelCase_			)
     for row_idx in range(UpperCAmelCase_			):
          # Print left spaces
          for _ in range(num_rows - row_idx - 1			):
               print(end=""" """			)
          # Print row values
          for col_idx in range(row_idx + 1			):
               if col_idx != row_idx:
                    print(triangle[row_idx][col_idx]					,   end=""" """			)
               else:
                    print(triangle[row_idx][col_idx]					,   end=""""""			)
          print()





def  _snake_case     (    UpperCAmelCase_  :					int			):

     if not isinstance(UpperCAmelCase_					,   UpperCAmelCase_			):
          raise TypeError("""The input value of 'num_rows' should be 'int'"""			)

     if num_rows == 0:
          return []
     elif num_rows < 0:
          raise ValueError(
              """The input value of 'num_rows' should be greater than or equal to 0"""			)

     A__										=  []
     for current_row_idx in range(UpperCAmelCase_			):
          A__										=  populate_current_row(UpperCAmelCase_					,   UpperCAmelCase_			)
          triangle.append(UpperCAmelCase_			)
     return triangle





def  _snake_case     (    UpperCAmelCase_  :					list[list[int]]					,   UpperCAmelCase_  :					int			):
     A__										=  [-1] * (current_row_idx + 1)
     # first and last elements of current row are equal to 1
     A__			,				A__										=  1, 1
     for current_col_idx in range(1					,   UpperCAmelCase_			):
          calculate_current_element(
              UpperCAmelCase_					,   UpperCAmelCase_					,   UpperCAmelCase_					,   UpperCAmelCase_			)
     return current_row





def  _snake_case     (    UpperCAmelCase_  :					list[list[int]]					,   UpperCAmelCase_  :					list[int]					,   UpperCAmelCase_  :					int					,   UpperCAmelCase_  :					int					,   ):
     A__										=  triangle[current_row_idx - 1][current_col_idx - 1]
     A__										=  triangle[current_row_idx - 1][current_col_idx]
     A__										=  above_to_left_elt + above_to_right_elt





def  _snake_case     (    UpperCAmelCase_  :					int			):

     if not isinstance(UpperCAmelCase_					,   UpperCAmelCase_			):
          raise TypeError("""The input value of 'num_rows' should be 'int'"""			)

     if num_rows == 0:
          return []
     elif num_rows < 0:
          raise ValueError(
              """The input value of 'num_rows' should be greater than or equal to 0"""			)

     A__										=  [[1]]

     for row_index in range(1					,   UpperCAmelCase_			):
          A__										=  [0] + result[-1] + [0]
          A__										=  row_index + 1
          # Calculate the number of distinct elements in a row
          A__										=  sum(divmod(UpperCAmelCase_					,   2			)			)
          A__										=  [
              temp_row[i - 1] + temp_row[i] for i in range(1					,   distinct_elements + 1			)
          ]
          A__										=  row_first_half[: (row_index + 1) // 2]
          row_second_half.reverse()
          A__										=  row_first_half + row_second_half
          result.append(UpperCAmelCase_			)

     return result





def  _snake_case     (    ):
     from collections.abc import Callable
     from timeit import timeit

     def benchmark_a_function(UpperCAmelCase_  :					Callable					,   UpperCAmelCase_  :					int			) -> None:
          A__										=  F"""{func.__name__}({value})"""
          A__										=  timeit(F"""__main__.{call}"""					,   setup="""import __main__"""			)
          # print(f"{call:38} = {func(value)} -- {timing:.4f} seconds")
          print(F"""{call:38} -- {timing:.4f} seconds"""			)

     for value in range(15			):  # (1, 7, 14):
          for func in (generate_pascal_triangle, generate_pascal_triangle_optimized):
               benchmark_a_function(UpperCAmelCase_					,   UpperCAmelCase_			)
          print()


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 benchmark()






