유클리드 호제법

728x90

유클리드 호제법이란,
숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b의최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미한다.

그럼, 계속해서 a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 b 가 0이 될때 까지 반복을
하면, 남는 a 값이 바로 최대 공약수 이다.

예를들어 숫자 2304 와 1440 이 있다고 생각해보자


2340 / 1440  = 1 ...864

1440 / 864   = 1 ...576

864 / 576    = 1 ...288

576 / 288    = 2 ... 0

나머지가 0일때 나누눈 수(288) 이 최대공약수가 된다

이거를 코드로 표현하면

import sys

a = 2304
b = 1440

# 최대 공약수
def gdc(x, y):
    while y > 0:
        x, y = y, x % y
    return x

print(gcd(2304,1440))

windy7271