GCD algorithm

 

GCD 알고리즘은 유클리드 호제법(Euclidean algorithm)으로도 불린다.

 

아래와 같은 원리를 이용하여 알고리즘을 짠다.

 

a lemma:

if a, b 가 정수이고 둘다 0이 아니면서

    a = b*q + r을 만족하는 q, r 이 정수이면

then 

    gcd(a, b) = gcd(b, r)

 

 

 

 

 

 

이를 코드에 그대로 옮기면, 최대공약수를 쉽게 구할 수 있다.

최소공배수는 A와 B를 곱하고, gcd(A, B)로 나누어 주면 구할 수 있다.

 

이를 이용하면 백준 문제를 쉽게 풀수있다.

 

 

#include <stdio.h>

int main() {
	int a, b, r;
	scanf("%d %d", &a, &b);
	int A = a;
	int B = b;
	while (b != 0) { r = a % b; a = b; b = r; }
	printf("%d\n", a);
	printf("%d\n", A*B / a);
	return 0;
}