유클리드 호제법

1. 유클리드 호제법이란?

    두 양의 정수, 혹은 다항식의 최대 공약수를 구하는 알고리즘

    ✨호제법: 서로 호(互), 나눌,덜 제(除)  즉, 서로 나누는것

 

    (큰 수를 작은 수로 나눈 나머지를 구한 후,

    그 나누었던 수와 나머지로 또 연산) => 이 과정을 반복(0이 될때까지)

    두 양의 정수 a,b(a>b)에 대하여 a=bq+r(0<=r<b)라 하면

    a,b의 최대공약수는 b,r의 최대공약수와 같다.

    즉, r=0이라면 a,b의 최대공약수는 b가 된다

2. 예시

    12345와 1234의 최대 공약수

    12345 % 1234 = 5

    1234 % 5 = 4

    5 % 4 = 1

    4 % 1 = 0   <- 여기서 나누었던 수가 최대공약수가 됨

3. 코드로 구현

<python> 

def gcd(a,b):
	if b==0:
        return a
    else:
        return gcd(b,a%b)  #나누었던 수와 나머지로 다시 수행
        
def lcm(a,b):
    return (a*b)//gcd(a,b)

🧨 이를 활용해 최소공배수도 구할 수 있음

 

int gcd(int a, int b){
	int r = a%b
    if (r=0){
    	return b;
    }
    return gcd(b,r)
}