[기초수학] 유클리드 호제법

[개념]

• x, y의 최대 공약수는 y, r의 최대 공약수와 같다.
• 이때 r은 ( x % y )

 

• 나머지가 0이 나오는 시점까지 연산하여 최대 공약수를 구할 수 있다.

 

 

 

 

 

---

[실습 1] 유클리드 호제법을 이용하여 최대공약수를 구해보자.

num1, num2 = map(int, input().split())
temp1, temp2 = num1,num2
while temp2>0 :
    temp = temp2
    temp2 = temp1 % temp2
    temp1 = temp
print('{}과 {}의 최대 공약수는 {}'.format(num1,num2,temp1))

for i in range(1,temp1+1):
    if temp1 % i == 0:
        print('{}과 {}의 공약수는 {}'.format(num1,num2,i))

'''
12 36
12과 36의 최대 공약수는 12
12과 36의 공약수는 1
12과 36의 공약수는 2
12과 36의 공약수는 3
12과 36의 공약수는 4
12과 36의 공약수는 6
12과 36의 공약수는 12
'''

코드 해석

temp1 % temp2 != 0 일 경우

temp1의 자리에는 temp2가 들어가고

temp2의 자리에는 temp1%temp2 의 나머지 연산 값이 들어간다.

 

주의할 점은 이때

temp1 = temp2

temp2 = temp1%temp2 를 하게되면

temp2 에는 기존의 나머지 연산 값이 아니라 이미 바뀐 값이 들어가 temp2%temp2 가 되기 때문에 0이 된다는 것이다.

 

따라서 temp라는 별도의 변수를 주어

temp = temp2

temp2 = temp1%temp2

temp1 = temp

를 해주어야 한다.

 

이는 외우지 않으면 문제 맞닿뜨렸을 때 갑자기 헷깔릴 수도 있을 것 같다.