[C] 유클리드 호제법을 이용해서 최대공약수와 최소공배수 구하기

(연관문제)

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

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

 

[소스코드 - 백준 2609 C 풀이]

#include <stdio.h>
// [baekjoon] 2609번 - 최대공약수와 최소공배수

int gcd(int min, int max) {		// 최대공약수 구하기
	int remainder = 1;
	while (remainder != 0) {
		remainder = max % min;
		max = min;
		min = remainder;
	}
	return max;
}

int lcm(int min, int max) {		// 최소공배수 구하기
	return min * max / gcd(min, max);
}

int main() {

	int a, b, min, max;
	scanf("%d %d", &a, &b);
	if (a > b) {
		max = a;
		min = b;
	}
	else {
		max = b;
		min = a;
	}
	printf("%d\n%d", gcd(min, max), lcm(min, max));
}

[소스코드 ver.2 (재귀함수 사용)]

#include <stdio.h>
// [baekjoon] 2609번 - 최대공약수와 최소공배수

int gcd(int max, int min) {		// 최대공약수 구하기(재귀 이용)
	if (min == 0)
		return max;
	else
		gcd(min, max%min);
}

int lcm(int max, int min) {		// 최소공배수 구하기
	return min * max / gcd(min, max);
}

int main() {

	int a, b, min, max;
	scanf("%d %d", &a, &b);
	if (a > b) {
		max = a;
		min = b;
	}
	else {
		max = b;
		min = a;
	}
	printf("%d\n%d", gcd(min, max), lcm(min, max));
}

 

 

C언어를 이용해서 최대공약수와 최소공배수를 구하는 방법은 여러가지가 있지만,

최대공약수 ( gcm, greatest common divisor )를 구하는 데는
유클리드 호제법을 이용할 수 있다.​

유클리드 호제법은 최대 공약수를 쉽게 구할 수 있는 방법으로
간단히 요약하면, 두 수 중에서, 큰 수(A)를 작은 수(B)로 나눈 다음
작은 수(B)를 큰 수를 작은 수로 나눈 나머지 (C) 로 나눠서  나머지가 0일 때까지 반복하면
이때의 나누는 수가 최대 공약수가 된다는 것이다.

유클리드 호제법으로 최대공약수를 구하는 과정

유클리드 호제법을 이용한 최대공약수의 과정을 그림으로 나타내 보았다.

유클리드 호제법으로 최대공약수를 구하는 과정 (2)

 

유클리드 호제법을 이용하면 위와 같이 큰 수의 최대공약수도 편하게 구할 수 있다.
자세한 내용은 아래 링크를 참고하면 좋을 듯싶다.

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

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

 

최소공배수 ( lcm, least common multiple )를 구하는 데는
최대공약수와 최소공배수의 관계를 생각하면 편하다.
두 수의 곱 = (두 수의 최대공약수)*(두 수의 최소공배수)이므로
lcm = 두 수의 곱 / gcd 가 된다.

해당 내용은 아래 링크 참조.

https://terms.naver.com/entry.naver?docId=925910&cid=47324&categoryId=47324 

최대공약수와 최소공배수의 활용