[C++] 최대공약수와 최소공배수 구하기

알고리즘을 푸는 도중에 최대공약수에 관한 문제가 나와 정리해봤다.

최대공약수

공약수는2개 이상 정수의 공통적인 약수를 말한다.
최대공약수란 공약수 중의 가장 큰 공약수를 말한다.

예를 들어, 2 와 4의 공약수는 1, 2 이다. 따라서, 최대공약수는 2 이다.

따라서 아래와 같이 함수를 사용해서 나타낼 수 있다.

int gcd(int a, int b){
	int n;

	while(b!=0){
		n=a%b;
		a=b;
		b=n;
	}
	
	return a;
}

 

최소공배수

공배수는 2개 이상의 정수의 공통적인 배수를 말한다.
최소공배수란 공배수 중의 가장 작은 공배수를 말한다.

예를 들어 2 와 4의 공배수는 4, 8, 12, ... 이다. 따라서, 최소공배수는 4 이다.

따라서 아래와 같이 함수를 사용해서 나타내보았다.
최소공배수의 경우 최대공약수를 알고있다면 두 수의 곱을 최대공약수로 나누게 되면 최소공배수를 구할 수 있다.

int lcm(int a, int b){
	return a*b / gcd(a, b);
}

 

예제 코드

#include <iostream>

using namespace std;

int gcd(int a, int b){
	int n;

	while(b!=0){
		n=a%b;
		a=b;
		b=n;
	}
	
	return a;
}

int lcm(int a, int b){
	return a*b / gcd(a, b);
}

int main(){
	int a, b;
	
	cin >> a >> b;
	
	cout << "최대공약수 : " << gcd(a, b) << " 최소공배수 : " << lcm(a, b);
	
	return 0;
}

입출력 결과

[입력]
2 4

[출력]
최대공약수 : 2 최소공배수 : 4