"""simple docstring"""







def     lowercase__( __SCREAMING_SNAKE_CASE							:  int  ,    __SCREAMING_SNAKE_CASE							:  int   ):
     while b:
          lowercase_							,						lowercase_			:       Any									=			b, a % b
     return a



def     lowercase__( __SCREAMING_SNAKE_CASE							:  int  ,    __SCREAMING_SNAKE_CASE							:  int   ):
     return a if b == 0 else euclidean_gcd_recursive(__SCREAMING_SNAKE_CASE  ,    a % b   )



def     lowercase__( ):
     print(F'''euclidean_gcd(3, 5) = {euclidean_gcd(3  ,    5   )}'''   )
     print(F'''euclidean_gcd(5, 3) = {euclidean_gcd(5  ,    3   )}'''   )
     print(F'''euclidean_gcd(1, 3) = {euclidean_gcd(1  ,    3   )}'''   )
     print(F'''euclidean_gcd(3, 6) = {euclidean_gcd(3  ,    6   )}'''   )
     print(F'''euclidean_gcd(6, 3) = {euclidean_gcd(6  ,    3   )}'''   )

     print(F'''euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3  ,    5   )}'''   )
     print(F'''euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5  ,    3   )}'''   )
     print(F'''euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1  ,    3   )}'''   )
     print(F'''euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3  ,    6   )}'''   )
     print(F'''euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6  ,    3   )}'''   )


if __name__ == "__main__":
       main()


"""simple docstring"""







from math import sqrt



def     lowercase__( __SCREAMING_SNAKE_CASE							:  int   ):

     if 1 < number < 4:
          # 2 and 3 are primes
          return True
     elif number < 2 or number % 2 == 0 or number % 3 == 0:
          # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
          return False

     # All primes number are in format of 6k +/- 1
     for i in range(5  ,    int(sqrt(__SCREAMING_SNAKE_CASE   ) + 1   )  ,    6   ):
          if number % i == 0 or number % (i + 2) == 0:
               return False
     return True



def     lowercase__( __SCREAMING_SNAKE_CASE							:  int = 1_00_01   ):
     lowercase_			:       str									=			0
     lowercase_			:       Optional[Any]									=			1
     while count != nth and number < 3:
          number += 1
          if is_prime(__SCREAMING_SNAKE_CASE   ):
               count += 1
     while count != nth:
          number += 2
          if is_prime(__SCREAMING_SNAKE_CASE   ):
               count += 1
     return number


if __name__ == "__main__":
       print(F"{solution() = }")

