문제풀이/초급
boj 2609 - 최대공약수와 최소공배수
씨플라스
2022. 6. 26. 23:50
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
문제 설명
간단한 문제이다. a와 b의 최소 공배수,최대 공약수를 구하면 된다.
풀이
전 게시글에서 최소 공배수에 대해 다루었으니
최대 공약수인 gcd값을 구하는 것만 알아보자.
증명은 넘어가고 코드를 보도록 하겠다.
주의할 점은 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;
}