최대 공약수와 최소 공배수 알고리즘

유클리드 호제법은 두 수의 최대 공약수는 큰 수에서 작은 수를 빼가며 어느 한 쪽이 0일때까지 반복하여 마지막에 0이 아닌 다른 한 수임을 이용하는 방법입니다.

예를 들어 

gcd(7,15) -> gcd(7,8) -> gcd(7,1) -> gcd(6,1) -> gcd(5,1) -> gcd(4,1) -> gcd(3,1) -> gcd(2,1) -> gcd(1,1) -> gcd(0,1)

gcd(6,8) -> gcd(6,2) -> gcd(4,2) -> gcd(2,2) -> gcd(0,2)

와 같이 진행하며 7과 15의 최대 공약수가 1, 6과 8의 최대 공약수가 2임을 알 수 있습니다.

max(a,b) - min(a,b) 연산은 max(a,b) % min(a,b) 연산으로 대체 할 수 있으므로 아래와 같이 정리 할 수 있습니다.

 

int gcd(int a,int b){
    int c = a % b;
    while(b){
    	a = b;
        b = c;
        c = a % b;
    }
    return b;
}

최소 공배수는 두 수의 곱에 최대 공약수를 나눠주면 됩니다.

int lcm(int a,int b){
      int g = gcd(a, b);
      return a * b / g;
}