최대공약수를 푸는 방법에는 유클리드 호제법이 있다.
유클리드 호제법
유클리드 호제법 코드
static int gcd(int x, int y){
if(y==0)
return x;
else{
return gcd(y, x%y);
}
}
이렇게 재귀적인 코드를 통해 최대공약수를 쉽게 구할 수 있다
최소공배수 구하기
최소공배수를 구하는 방법은 매우 쉽다. 두 수의 곱에 최대공약수를 나눠주면 되기 때문이다
최소공배수 코드
static int lcm(int x, int y){
return x*y/gcd(x,y);
}