반응형
알고리즘 분류 : 수학
최대공약수(GCD; greatest common divisor)는 유클리드 호제법(Euclidean algorithm)을 이용하여 구현할 수 있다.
- r은 x를 y로 나눈 나머지 (r = x%y)
- GCD(x, y) = GCD(y, r) 를 r이 0이 될 때까지 반복적으로 수행
- r이 0일 때, y는 최대공약수이다.
최소공배수(LCM; least common multiple)는 미리 구한 최대공약수를 이용하여 구현할 수 있다.
- g = GCD(x, y)
- LCM = (x*y)/g
C++ 소스코드
#include <iostream> using namespace std; int gcd(int x, int y) { while (y != 0) { int r = x%y; x = y; y = r; } return x; } int lcm(int x, int y) { return (x*y)/gcd(x,y); } int main() { int a, b; cin >> a >> b; cout << gcd(a,b) << '\n'; cout << lcm(a,b) << '\n'; return 0; }
✓ gcd 함수는 재귀함수로 구현할 수 있다.
int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x%y); }
Python 3 소스코드
def gcd(x, y): while y is not 0: r = x%y x = y y = r return x def lcm(x, y): return (x*y)//gcd(x,y) a, b = map(int, input().split()) print(gcd(a,b)) print(lcm(a,b))
참고
반응형