최대공약수(a, b) = 최대공약수(b, r)
r = a와 b를 나눈 나머지 (단, a > b)
#while문 사용
int gcd(int a, int b) {
while(b!=0) {
int r=a%b;
a=b;
b=r;
}
return a;
}
#재귀함수 사용
int gcd(int a, int b) {
if(a%b ==0) {
return b;
}
return gcd(b, a%b);
}
최소공배수
ab = 최대공약수x최소공배수 이므로
최소공배수 = a*b/gcd
int lcm(int a, int b) {
return a*b / gcd(a,b);
}