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

문제링크 : www.acmicpc.net/problem/2609

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

유클리드 호제법 사용

유클리드 호제법 : 두 수가 서로 상대수를 나눠서 최대공약수를 구하는 알고리즘

예제) 78696과 19332의 최대공약수를 구하는 방법

78696 ＝ 19332×4 ＋ 1368 1

9332 ＝ 1368×14 ＋ 180

1368 ＝ 180×7 ＋ 108

180 ＝ 108×1 ＋ 72

108 ＝ 72×1 ＋ 36

72 ＝ 36×2 ＋ 0

=> 최대공약수 : 72

+)참고 

호제법 : 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

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

최대공약수는 유클리드 호제법으로 구하기, 최소공배수는 (최대공약수*최소공배수 = 두수의 곱) 성질 이용

#include <iostream>
using namespace std;

int gcd(int a, int b) {
	int n = 1;
	while (b != 0) {
		n = a % b;
		a = b;
		b = n;
	}
	return a;
}
int main() {
	int A = 0;
	int B = 0;
	cin >> A >> B;
	cout << gcd(A, B) << "\n" << (A*B) / gcd(A, B);

}

 

 

+) 유클리드 호제법을 알기 이전에 했던 구현인데 백준에서는 계속 틀렸다네요. 어디가 틀린걸까요?

#include <iostream>
using namespace std;

int main() {
	int A = 0;
	int B = 0;
	cin >> A >> B;

	int maximum = 1;
	long minimum = 1;

	for (int i = 2; (i <= A) && (i <= B); i++) {
		if ((A%i == 0) && (B%i == 0)) {
			maximum *= i;
			A /= i;
			B /= i;
		}
	}
	minimum = A * B * maximum;
	cout << maximum << "\n" << minimum;
	return 0;
}

-> 위의 코드의 문제점은 같은 수가 반복되어 약수일 경우 그 부분을 체크할 수 없다는 점이었습니다.

     ex) 12와 4의 최대공약수가 4임에도 2를 한번만 체크하기 때문에 최대공약수를 2로 출력했습니다.

이를 수정한 코드는 아래와 같습니다.

#include <iostream>
using namespace std;
int main() {
	int A = 0;
	int B = 0;
	cin >> A >> B;

	int maximum = 1;
	long minimum = 1;

	int i = 2;
	while ((i <= A) && (i <= B)) {
		if ((A%i == 0) && (B%i == 0)) {
			maximum *= i;
			A /= i;
			B /= i;
		}
		else {
			++i;
		}
	}
	minimum = A * B * maximum;
	cout << maximum << "\n" << minimum;
	return 0;
}