코드트리: 최대공약수와 최소공배수

 

 

---

 

문제

n, m 입력받고, n과 m의 최소 공배수를 출력하는 프로그램을 작성하시오.

 

 

 

 

실행 결과

 

 

 

 

 

코드(c++)

#include <iostream>
using namespace std;

int gcd(int a, int b) {  // 최대공약수
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}

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

int main() {
	int n, m;
	cin >> n >> m;
	cout << lcm(n, m);
	return 0;
}

 

 

 

 

코드 설명

1. 최대공약수 gcd

유클리드 알고리즘이란 두 개의 정수의 최대공약수를 결정하는 데 사용되는 알고리즘이다.

두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 호제법이라고도 부른다.

두 정수가 서로소(relatively prime)인 경우, 유일한 공통 양의 정수 인수는 1이라는 것을 이용한다.

과정: 두 수를 나눈다. 그런 다음 나머지를 취하여 이전의 두 수 중 작은 값으로 대체한다.

이 과정을 나머지가 0이 될 때까지 계속 반복한다.

 

 

2. 최소공배수 lcm

a와 b의 최소공배수는 두 수의 곱 나누기 a와 b의 최대공약수임을 이용한다.

두 수의 곱을 하면 최대공약수가 공통으로 곱해져 있으므로

최대공약수로 한 번 나눠주면 두 수의 최소공배수를 얻을 수 있다.

 

 

 

---

 

문제 출처:

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석