최대공약수와 최소공배수

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	82396	47590	38651	58.309%

문제

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

입력

첫째 줄에는 두 개의 자연수가 주어진다.

이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,

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

예제 입력 1

24 18

예제 출력 1

6
72

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 1번

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 고등부 1번

• 데이터를 추가한 사람: circlecho, jsh587

알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법

---

알고리즘 – 유클리드 호제법(Euclidean Algorithm) / GCD + LCM

---

해당 문제를 해결하려면 유클리드 호제법을 알아야한다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은

2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

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

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

// 유클리드 호제법
// C++ 기본 코드

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

정리하자면

2개의 자연수 A, B에(A>B) 대해서

A를 B로 나눈 나머지를 r이라 하면, A와 B의 최대공약수는 B와 r의 최대공약수와 같다.

이 성질에 따라, B를 r로 나눈 나머지 r’를 구하고,

다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때

나누는 수가 a와 b의 최대공약수이다.

최소공배수는 두 수 A,B를 곱한 값을 최대공약수로 나눈 값이다.

// 유클리드 호제법
// C++ 기본 코드

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


// 최소공배수
// 두 수 A,B를 곱한 값을 최대공약수로 나눈 값이다.
int lcm(int a, int b) {

	return (a * b) / gcd(a, b);
}

통과된 코드

#include <iostream>

using namespace std;

int A, B, temp, maxA, minB;


// 유클리드 알고리즘
// 최대공약수
int gcd(int a, int b)
{
	int c;
	while (b)
	{
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

// 최소공배수
// 두 수 A,B를 곱한 값을 최대공약수로 나눈 값이다.
int lcm(int a, int b) {

	return (a * b) / gcd(a, b);
}

int main()
{
	cin >> A >> B;
	cout << gcd(A, B) << "\n";
	cout << lcm(A, B);

	return 0;
}

유클리드 호제법을 모르면 해결하기 어려운 문제