[Algorithm] 코드로 최대공약수(GCD)와 최소공배수(LCM) 구하기
업데이트(2018.04.29): a mod b 부분 추가
유클리드 호제법을 통해서 최대공약수를 공하고 최대공약수를 통해서 최소공배수를 구해보자
환경 및 선수조건
- C++
최대공약수 공식(유클리드 호제법)
- a,b: 최대공약수를 구하고자 하는 두 수
- r: a를 b로 나눈 나머지 = ( a%b ) = ( a mod b )
- 식:
gcd(a,b) = gcd(b,r)
코드(최대공약수)
example.cpp
int gcd(int a, int b){
while(b!=0){
int r = a%b;
a= b;
b= r;
}
return a;
}
최소공배수 공식(최대공약수를 이용)
- a,b: 최소공배수를 구하고자 하는 두 수
- gcd(a,b): a와b의 최대공약수
- (최소공배수 * 최대공약수 = a * b)를 이용
- 식:
a * b / gcd(a,b)
코드(최소공배수)
example.cpp
int gcd(int a, int b){
while(b!=0){
int r = a%b;
a= b;
b= r;
}
return a;
}
int lcm(int a, int b){
return a * b / gcd(a,b);
}