[C++] 유클리드 호제법, 최대 공약수, 최소 공배수 구하기

자꾸 헷갈려서 정리해놓는 GCD, LCM

 

최대 공약수 & 최소 공배수 구하기

#include <bits/stdc++.h>
using namespace std;


// a와 b의 최대 공약수 구하기
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int a, b; cin >> a >> b;
	int maxN = max(a, b);
	int minN = min(a, b);

	// a와 b의 최소 공배수 : (a * b) / (a*b의 최대 공약수)
	cout << a * b / gcd(minN, maxN) << endl;

}

 

헷갈려 @_@