


'''simple docstring'''
import random

def 					lowerCamelCase_ ( __UpperCamelCase					:       int		)					->	bool:







     """simple docstring"""
     _A				=							num - 1
     _A				=							0

     while s % 2 == 0:
          _A				=							s // 2
          t += 1

     for _ in range(5		):
          _A				=							random.randrange(2							,    num - 1		)
          _A				=							pow(__UpperCamelCase							,    __UpperCamelCase							,    __UpperCamelCase		)
          if v != 1:
               _A				=							0
               while v != (num - 1):
                    if i == t - 1:
                         return False
                    else:
                         _A				=							i + 1
                         _A				=							(v**2) % num
     return True

def 					lowerCamelCase_ ( __UpperCamelCase					:       int		)					->	bool:







     """simple docstring"""
     if num < 2:
          return False

     _A				=							[
         2,
         3,
         5,
         7,
         1_1,
         1_3,
         1_7,
         1_9,
         2_3,
         2_9,
         3_1,
         3_7,
         4_1,
         4_3,
         4_7,
         5_3,
         5_9,
         6_1,
         6_7,
         7_1,
         7_3,
         7_9,
         8_3,
         8_9,
         9_7,
         1_0_1,
         1_0_3,
         1_0_7,
         1_0_9,
         1_1_3,
         1_2_7,
         1_3_1,
         1_3_7,
         1_3_9,
         1_4_9,
         1_5_1,
         1_5_7,
         1_6_3,
         1_6_7,
         1_7_3,
         1_7_9,
         1_8_1,
         1_9_1,
         1_9_3,
         1_9_7,
         1_9_9,
         2_1_1,
         2_2_3,
         2_2_7,
         2_2_9,
         2_3_3,
         2_3_9,
         2_4_1,
         2_5_1,
         2_5_7,
         2_6_3,
         2_6_9,
         2_7_1,
         2_7_7,
         2_8_1,
         2_8_3,
         2_9_3,
         3_0_7,
         3_1_1,
         3_1_3,
         3_1_7,
         3_3_1,
         3_3_7,
         3_4_7,
         3_4_9,
         3_5_3,
         3_5_9,
         3_6_7,
         3_7_3,
         3_7_9,
         3_8_3,
         3_8_9,
         3_9_7,
         4_0_1,
         4_0_9,
         4_1_9,
         4_2_1,
         4_3_1,
         4_3_3,
         4_3_9,
         4_4_3,
         4_4_9,
         4_5_7,
         4_6_1,
         4_6_3,
         4_6_7,
         4_7_9,
         4_8_7,
         4_9_1,
         4_9_9,
         5_0_3,
         5_0_9,
         5_2_1,
         5_2_3,
         5_4_1,
         5_4_7,
         5_5_7,
         5_6_3,
         5_6_9,
         5_7_1,
         5_7_7,
         5_8_7,
         5_9_3,
         5_9_9,
         6_0_1,
         6_0_7,
         6_1_3,
         6_1_7,
         6_1_9,
         6_3_1,
         6_4_1,
         6_4_3,
         6_4_7,
         6_5_3,
         6_5_9,
         6_6_1,
         6_7_3,
         6_7_7,
         6_8_3,
         6_9_1,
         7_0_1,
         7_0_9,
         7_1_9,
         7_2_7,
         7_3_3,
         7_3_9,
         7_4_3,
         7_5_1,
         7_5_7,
         7_6_1,
         7_6_9,
         7_7_3,
         7_8_7,
         7_9_7,
         8_0_9,
         8_1_1,
         8_2_1,
         8_2_3,
         8_2_7,
         8_2_9,
         8_3_9,
         8_5_3,
         8_5_7,
         8_5_9,
         8_6_3,
         8_7_7,
         8_8_1,
         8_8_3,
         8_8_7,
         9_0_7,
         9_1_1,
         9_1_9,
         9_2_9,
         9_3_7,
         9_4_1,
         9_4_7,
         9_5_3,
         9_6_7,
         9_7_1,
         9_7_7,
         9_8_3,
         9_9_1,
         9_9_7,
     ]

     if num in low_primes:
          return True

     for prime in low_primes:
          if (num % prime) == 0:
               return False

     return rabin_miller(__UpperCamelCase		)

def 					lowerCamelCase_ ( __UpperCamelCase					:       int = 1_0_2_4		)					->	int:







     """simple docstring"""
     while True:
          _A				=							random.randrange(2 ** (keysize - 1)							,    2 ** (keysize)		)
          if is_prime_low_num(__UpperCamelCase		):
               return num


if __name__ == "__main__":
    lowerCAmelCase						=					generate_large_prime()
    print(("""Prime number:""", num))
    print(("""is_prime_low_num:""", is_prime_low_num(num)))









'''simple docstring'''
from __future__ import annotations

def 					lowerCamelCase_ ( __UpperCamelCase					:       list							,    __UpperCamelCase					:       int | None = None							,    __UpperCamelCase					:       int | None = None		)					->	None:







     """simple docstring"""
     if start is None:
          _A				=							0

     if end is None:
          _A				=							len(__UpperCamelCase		) - 1

     if start >= end:
          return

     _A				=							(start + end) // 2

     slowsort(__UpperCamelCase							,    __UpperCamelCase							,    __UpperCamelCase		)
     slowsort(__UpperCamelCase							,    mid + 1							,    __UpperCamelCase		)

     if sequence[end] < sequence[mid]:
          _A		,				_A				=							sequence[mid], sequence[end]

     slowsort(__UpperCamelCase							,    __UpperCamelCase							,    end - 1		)


if __name__ == "__main__":
    from doctest import testmod

    testmod()





