유클리드 호재법 (재귀)

두 정수값의 최대 공약수GCD 재귀로 구하기

• 두개의 정숫값을 직사각형 두 변의 길이라고 할 때

Q. 직사각형 안을 정사각형 여러개로 가득 채워 나간다. 이렇게 만들 수 있는 정사각형 가운데 가장 작은 정사각형의 변의 길이를 구하라.

최종 정사각형 변의 길이인 2가 8과 22의 최대 공약수!

유클리드 호제법 Euclidean agorithm

두 정수 x와 y의 최대 공약수를 gcd(x,y)라 표기
x = az와 y = bz 를 만족하는 정수 a,b와 최대의 정수 z가 존재할 때 z는 gcd(x,y)

최대 공약수 구하기 )
y가 0이면 .... x
y가 0이 아니면 ...gcd(y,x%y)

def gcd(x:int,y:int)->int:
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

if __name__ == '__main__':
    print('두 정수값의 최대 공약수를 구합니다.')
    x = int(input('첫 번째 정숫값을 입력하세요 : '))
    y = int(input('두 번째 정숫값을 입력하세요 : '))

    print(f'두 정숫값의 최대 공약수는 {gcd(x,y)}입니다.')

22 와 8의 최대공약수 구하기

gcd(22,8)

y != 0 : (8,22%8) => (8,6)
y != 0 : (6,8%6) => (6,2)
y != 0 : (2,6%2) => (2,0)
y == 0 : 2
22와 8의 최대 공약수는 2 이다.