백준 / 수학 / 2609번 / 최대공약수와 최소공배수 / C++

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1 

24 18

예제 출력 1 

6

72

 

#include <iostream>
using namespace std;

int gcd(int n1, int n2) { // 최대공약수 
	return n2 ? gcd(n2, n1%n2) : n1;
}

int lcm(int n1, int n2) { // 최소공배수 
	return n1 * n2 / gcd(n1, n2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n1, n2;
	cin >> n1 >> n2;
	
	cout << gcd(n1, n2) << '\n';
	cout << lcm(n1, n2) << '\n';
	
	return 0;
}

---

최대공약수와 최소공배수가 뭔지는 알지만 알고리즘으로 구현하기가 생각보다 막막하다.

그래서 찾아보았는데, 새로운 개념과 식을 알게되었다.

 

일단 최소공배수부터 보면, 최소공배수는 두 수를 곱한뒤 두 수의 최대공약수로 나눠주면 구해진다.

물론 algorithm헤더에 다 구현되어 있지만 알아두면 매우 유용할 것 같다.

 

최대공약수는 유클리드 호제법이라는 개념을 적용했다.

호제법이라는 말은, 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘을 나타낸다.

두 개의 자연수 a, b가 있고 a를 b로 나눈 나머지를 r이라 하자. (단, a>b)

이때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여

나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

예시로 1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어떨어진다.

따라서, 최대공약수는 21이다.

 

우리가 알고리즘 코드로 나타낼 것은 위의 밑줄친 부분이다.

a % b = r이고, gcd(a, b) = gcd(b, r) = gcd(b, (a%b)) 이다.

다시 계속 반복하게 되면, gcd(b,r) = gcd(r, r') = gcd((a%b), (b%(a%b))) 이다.

이것을 나머지가 0이 될때까지 하고, 그때의 나누는 수가 최대공약수가 되는것이다.

여기서 반복을 찾을 수 있는데 이것을 재귀로 나타내면,

int gcd(int n1, int n2) {
	return n2 ? gcd(n2, n1%n2) : n1;
}

 

위의 코드가 된다.

n2가 0이 아니면 재귀를 돌고, n2가 0이게 되면 그때 나누는 수인 n1이 최대 공약수가 되는것이다.

물론 재귀로 나타내지 않는 방법도 있다.

int gcd(int a, int b)
{
    int c;
	while(b)
	{
		c = a % b;
		a = b;
		b = c;
	}
    return a;
}

단지 변수를 하나 더 두어서 순서만 바꾸면서 마찬가지로 b가 0이 될때까지 반복하는 것이다.