[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);
}

참고자료

• 코드플러스 알고리즘 기초