기본 유클리드 알고리즘을 위한 Python 프로그램

이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.

문제 설명 − 두 개의 숫자가 주어지면 이 두 숫자의 gcd를 계산하여 표시해야 합니다.

두 숫자의 GCD 최대 공약수는 두 숫자를 모두 나눌 수 있는 가장 큰 숫자입니다. 여기서 우리는 gcd를 계산하기 위해 유클리드 접근 방식을 따릅니다. 즉, 숫자를 반복적으로 나누고 나머지가 0이 되면 중지합니다.

이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -

예시

# euclid algorithm for calculation of greatest common divisor
def gcd(a, b):
   if a == 0 :
      return b
   return gcd(b%a, a)
a = 11
b = 15
print("gcd of ", a , "&" , b, " is = ", gcd(a, b))

출력

gcd of 11 & 15 is = 1

모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.

결론

이 기사에서는 기본 유클리드 알고리즘을 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.