최대공약수 / 최소공배수

GCD를 구할 때에는 유클리드 알고리즘을 사용한다.

두 자연수 a, b에 대해 (a > b)

a를 b로 나눈 나머지 n이 0이면 b가 GCD이다.

n이 0이 아니면,

a = b; b = n;으로 대입한 뒤 다시 반복한다.

 

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

int gcd(int a, int b){
    // a가 b보다 큰 값으로 만듦.
    if(a < b){
    	int tmp = a;
        a = b;
        b = tmp;
    }
    
    // 반복문으로 구현한 유클리드 알고리즘
    while(b != 0){
    	int n = a%b;
        a = b;
        b = n;
    }
    return a;
}

 

LCM을 구할 때에도 유클리드 호제법을 이용한다.

자연수 a와 b에 대해,

LCM = a*b / gcd(a, b)를 만족한다.