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

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/2609

 

 

 

두 수 A, B의 최대공약수가 G라면 A = a * G, B = b * G로 정의할 수 있다.

그러면 최소공배수는 a * b * G = A * B / G 가 된다.

 

최대공약수는 유클리드 호제법으로 구할 수 있다.

A % B = R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. (A ≥ B) 

위키백과 예시

즉, B가 0이 아닌 경우 gcd(B, A % B)를 구한다.

이 과정을 B가 0이 되는 경우에 A를 return하면 된다.

 

최소공배수의 경우 A * B / G의 경우 A * B 연산에 의해 overflow가 발생할 수 있다.

따라서 나누기를 먼저해서 (A / G * B) overflow를 방지한다.

#include <stdio.h>

int gcd(int a, int b)
{
	return (b) ? gcd(b, a % b) : a;
}

int lcm(int a, int b)
{
	return a / gcd(a, b) * b;
}

int main(void)
{
	int a, b;

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

	printf("%d\n", gcd(a, b));
	printf("%d\n", lcm(a, b));

	return 0;
}