boj 2609 - 최대공약수와 최소공배수

boj.kr/2609

2609번: 최대공약수와 최소공배수

문제 설명

간단한 문제이다. a와 b의 최소 공배수,최대 공약수를 구하면 된다.

 

풀이

전 게시글에서 최소 공배수에 대해 다루었으니

최대 공약수인 gcd값을 구하는 것만 알아보자.

증명은 넘어가고 코드를 보도록 하겠다.

(유클리드 호제법 - 나무위키 (namu.wiki))

주의할 점은 a가 b보다 크도록 하고 실행해야한다.

int gcd(int a,int b){

if(a%b==0)return b;

else return gcd(b,a%b);

}

더 간결하게 짜는 법은 이와 같다.

(삼항 연산자를 사용하도록 하자)

int gcd(int a,int b){
return a%b?gcd(b,a%b):b;
}