백준 2609 / 최대공약수 최소공배수

문제

정리

• 두 수 a와 b의 최대공약수(g)는 a와 b의 공통된 약수 중에서 가장 큰 정수이다.
• 최대공약수가 1인 두 수를 '서로소'라고 한다.

방법 1

최대공약수를 구하는 가장 쉬운 방법은 2부터 min(a, b)까지의 모든 정수로 나누어 보는 방법이다.

방법 2

유클리드 호제법(Euclidean algorithm)
a를 b로 나눈 나머지를 r이라고 했을 때 gcd(a,b) = gcd(b,r)과 같다
r이 0이면 그 때 b가 최대 공약수이다.

코드

c++

#include <iostream>

using namespace std;
/*
solution 1
int gcd(int a, int b) {
	int g = 1;

	for (int i = 2; i <= min(a, b); i++) {
		if (a % i == 0 && b % i == 0) {
			g = i;
		}
	}

	return g;
} */
// solution 2
// 재귀함수 적용
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}


int main() {
	int n1 = 0, n2 = 0;

	cin >> n1 >> n2;

	int g = gcd(n1, n2);

	cout << g << '\n' << n1 * n2 / g << '\n';

	return 0;
}

java

출처 : https://www.acmicpc.net/problem/2609