[C++]백준2609 최대공약수와 최소공배수

29 Nov 2022 in Study on Algorithm

백준2609 최대공약수와 최소공배수 링크

문제

예제 입력

---

코드

#include<iostream>
using namespace std;

// 유클리드호제법
int get_gcd(int u, int v) {
	int tmp;
	while (v) {
		tmp = u % v;
		u = v;
		v = tmp;
	}

	return u;
}

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

	int a, b;
	cin >> a >> b;

	cout << get_gcd(a, b) << '\n';
	cout << a * b / get_gcd(a, b) << '\n';
}

설명

기본적으로 C/C++의 기본 입출력함수를 혼합하여 사용되게 만들었지만 그만큼 실행속도에서 차이가 생기기 때문에 설정을 해주며 입력을 받아 최대공약수는 서로 나누고(u / v) 나온 나머지 값(tmp)으로 다시 나눈 값(v)을 나누는 것을 반복(v / tmp) 계산하여 구합니다. 그리고 최소공배수는 두 수를 곱한 값을 최대공약수로 나누면 됩니다.

#include<algorithm>
//algorithm 헤더 파일에 __gcd() 함수가 이미 있습니다.
cout << _gcd(a, b) << '\n';
cout << a * b / __gcd(a, b) << '\n';

---

결과