[python] 반복문과 재귀 호출을 사용하여 두 수의 최대 공약수 구하기

문제 설명

최대 공약수란 2개의 숫자를 소인수분해한 후에 결과가 중복되는 부분을 찾아 곱셈한 수
12 = 2 * 2* 3 / 18 = 2*3*3 중복된 부분은 2*3으로 최대 공약수는 6이다.
하지만 우리는 유클리드 호제법을 통해 최대 공약수를 구해본다.
예시) 192%72=48 나머지는 48 여기서 다시 72 와 48을 나눈다. 72 % 48=24 다음 과정은 48 % 24 =0
나머지가 0이 되므로 연산을 중지하고 이전에 구한 나머지 24가 192, 72 의 최대 공약수가 된다.

반복문을 통한 코드

def f(a,b):
  if a > b :
    pass
  else :
    a, b = b, a

  while b > 0:
    c = b
    b = a%b
    a = c
  return a
n, m = map(int, input("두 수를 입력하시오 :").split())
print(f'{n}와 {m}의 최대 공약수 : {f(n,m)}')

재귀 호출을 통한 코드

n, m = map(int, input("두 수를 입력하시오 :").split())

def f(a,b):
  if a > b :
    pass
  else :
    a, b = b, a
  if b == 0 :
    return a
  return f(b, a%b)
print(f'{n}와 {m}의 최대 공약수 : {f(n,m)}')

해설

변수 c는 큰 수와 작은 수 중 작은 수의 값을 미리 받아 변수 a에 대입한다. (반복 과정 후 나머지가 0이 됐을 때 이전의 작은 수를 알기 위함이다.)