이론공부
유클리드 호제법, 최대공약수(GCD) 구하기
yoo.o
2020. 10. 14. 04:08
반응형
유클리드 호제법이란
최대공약수를 구하기 위해서는 유클리드 호제법을 사용하면 된다.
호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.
먼저 1071을 1029로 나눈다. 42라는 나머지가 나온다.
만약 1029가 42로 나누어진다면 1071 = 42 * n이 될텐데 42로 안나눠지니까 42는 최대공약수가 될 수 없다.
그 후 1029을 42로 나눠서 21을 얻는다.
이때 42는 21로 나누어지기 때문에 21을 약수로 가진다.
따라서 최대공약수는 21이다.
글로 읽으면 복잡한데 결국 1071은
1071 = (1029 * 1) + 42
= ((42 * k) * 1) + 42
= (((21*2) *k) *1) + (21*2)
= 21 * (k+2)
로 쓰일수 있다는걸 생각해보면 이해하는데 도움이 된다.
파이썬 코드
def gcd(a, b):
while b is not 0:
mod = a % b
a = b
b = mod
return a
참고로 파이썬에는 이미 GCD 모듈이 있다.
from math import gcd
result = gcd(a, b)
여러 수의 최대공약수
세 개 이상의 최대공약수를 구할때는 두개씩 구해주면 된다.
result = gcd(gcd(a, b), c)
반응형