import math




def    __lowerCAmelCase   (    A_ :			int       )     ->	bool:

  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(math.sqrt(__UpperCAmelCase       ) + 1       )    ,						6       ):
    if number % i == 0 or number % (i + 2) == 0:
      return False
  return True




def    __lowerCAmelCase   (    A_ :			float = 0.1       )     ->	int:
  __UpperCAmelCase         =							3
  __UpperCAmelCase         =							3

  while primes / (2 * j - 1) >= ratio:
    for i in range(j * j + j + 1    ,						(j + 2) * (j + 2)    ,						j + 1       ):
      primes += is_prime(__UpperCAmelCase       )
    j += 2
  return j


if __name__ == "__main__":
       import doctest

       doctest.testmod()











"""simple docstring"""





def   a    (     __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    int  )    ->							int:
						while b:
												__magic_name__,			__magic_name__:	Optional[int]							=       b, a % b
						return a



def   a    (     __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    int  )    ->							int:
						return a if b == 0 else euclidean_gcd_recursive(__UpperCAmelCase      ,   a % b  )



def   a    (     )    ->							List[Any]:
						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()



