[Baekjoon] Class2 16 - 최대공약수와 최소공배수 [2609]

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

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

입력

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

출력

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

생각해볼점

유클리드 호제법을 활용하면 된다.
위키피디아 링크
큰 수를 작은 수로 나눈 나머지를 구한다. 이 때 작은 수를 a, 나머지를 b라고 하면 a를 다시 b로 나눈 나머지로 구해 이번엔 b를 a, 이 때의 나머지를 b로 둔다. 이 과정을 반복하다 나머지가 0이 될 때의 a가 최대공약수가 된다.
최소공배수는 큰 수와 작은수의 곱을 최대공약수로 나누면 된다.

코드 구현

#include <stdio.h>

int main()
{
	int	a, b, mul, temp;

	scanf("%d %d", &a, &b);

	mul = a * b;
	if (a < b)
	{	
		temp = a;
		a = b;
		b = temp;
	}

	while (a % b != 0)
	{	
		temp = a;
		a = b;
		b = temp % a;
	}
	
	printf("%d\n%d", b, mul / b);
	return (0);
}