[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 최대공약수와 최소공배수 (2609)

 

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 최대공약수와 최소공배수 (2609)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 최대공약수와 최소공배수 (2609)

 

---

 

2609번: 최대공약수와 최소공배수

[ 문제 ]

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

[ 입력 ]

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

[ 출력 ]

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

---

[ 코드 ]

#include<iostream>
using namespace std;

int gcd(int a, int b) {
	if (b == 0)
	{
		return a;
	}
	else
	{
		return gcd(b, a % b);
	}
}

int main() {
	int A, B; // 두 개의 입력
	cin >> A >> B; 

	// [ 최대공약수 출력 ]
	// 최대공약수 (GCD) : A와 B의 공통된 약수 중에서 가장 큰 정수

	// 1. 일반풀이
	int result = 1; // 1,1일때는 소수가 1이기 때문에, 이를 기본값으로 놓아야 함.

	for (int i = 2; i <= min(A,B); i++)
	{
		if (A % i == 0 && B % i == 0)
		{
			result = i;
		}
	}
	cout << result << '\n';

	// 2. 유클리드 호제법 활용
	cout<< gcd(A, B)<<'\n';


	// [ 최소공배수 출력 ]
	// 최소공배수 (LCM) : A*B/GCD()
	cout<<(A*B)/gcd(A, B)<<'\n';

	return 0;
}

---

* 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :)