유클리드 호제법을 이용한 최대공약수, 최대공배수

유클리드 호제법

 

2개의 정수의 최대 공약수와 최대 공배수를 구하는 방법이다. 

두 개의 정수 A, B가 있을 때 (A>=B) A%B, 즉 A를 B로 나눴을 때 나머지 R가 있을 때,

A와 B의 최대공약수가 B와 R의 최대공약수와 같다는 성질을 이용하는 것이다.

 

그래서 A와 B의 최대공약수를 구하기 위해서는

A%B, B%R을 반복하면 된다. 

 

int main(void) {

	int n1, n2; 
	int max, min;
	int tmp;
	scanf("%d %d", &n1, &n2);

	if (n1 > n2) {
		max = n1; 
		min = n2;
	}
	else {
		max = n2;
		min = n1;
	}

	while (min) {
		int tmp = max % min;
		max = min;
		min = tmp;
	}
	printf("최대공약수: %d\n", max);
	printf("최소공배수: %d", n1 * n2 / max);
}