유클리드 호제법 : 두 수의 최대공약수를 구하는 알고리즘`
- 주어진 두 값에서 큰 값 % 작은 값 연산을 하여 나머지를 구한다.
- 나머지가 0이 아니라면, 작은 값 % 나머지 값을 계속 진행한다.
- 나머지가 0이 되면, 마지막 계산에서 나누는 수로 사용된 숫자가 두 수의 최대공약수가 된다.
def gcd(a, b):
if (b>a) : a,b = b,a
while(b):
a = a%b
a,b = b,a
return a
def gcd(a, b):
if (b>a) : a,b = b,a
return b if not(a%b) else gcd(b, a%b)
주어진 두 값을 곱한 다음 최대공약수로 나누어준다.