최대 공약수 최소 공배수

 

최대 공약수, 최소 공배수는 코딩테스트 등에서 은근 많이 쓰이는 개념이다.

식을 외워두면 금방 구하기 떄문에 특히 최대공약수 공식은 외워 두는게 좋다.

 

최대공약수 (Greatest Common Divisor, GCD) 

유클리드 호재법으로 구할 수 있다.

재귀를 이용하면 짧은 코드를 만들 수 있다.

나머지가 0이 될 때까지 두 수의 자리를 바꿔가면서 구하면 된다.

단, 다음의 식은 a >= b 이므로, 

max 와 min 등으로 순서를 정하거나, a > b? GCD(a, b) : GCD(b, a) 등을 써서 인자 순서에 주의하자.

// 최대공약수 재귀 함수. 한쪽이 0이 될 때까지 스왑하면서 나머지를 구한다.
public int GCD(int a, int b)
{
     if(b == 0) return a;
     else return GCD(b, a % b);
}

 

반복문을 사용한 예시

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

최소공배수 (Least Common Multiple: LCM)

두 수를 곱한다음, 최대공약수로 나눠주기만 하면 되기 때문에 필연적으로 최대공약수를 구해야한다.

public int LCM(int a, int b)
{
    return (a * b) / GCD(a, b);
}

 

 

기약분수 만들기

기약분수(분자와 분모의 공약수가 1뿐인 분수)를 만드려면 분자와 분모의 최대 공약수가 1이 될 때까지 최대 공약수를 구해서 나눠주면된다.

while(true)
{
    int gcd = GCD(parent, child);
    if(gcd > 1)
    {
        child /= gcd;
        parent /= gcd;
    }
    else
    {
        break;
    }
}