유클리드 호제법
호제(互除) : 서로 나눔
최대 공약수 (gcd)
재귀 처리
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
C++
복사
반복 처리
int gcd(int a, int b) {
int c;
while(b) {
c = a % b;
a = b;
b = c;
}
return a;
}
C++
복사
최소 공배수 (lcm)
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
C++
복사