정올 1658 : 최대공약수, 최소공배수 (+유클리드 호제법)

방법 1: 처음부터 확인해가면서 약수를 구함 -> 숫자가 커지면 시간이 오래걸린다.

#include <stdio.h>

// 최대공약수
int gcd_get(int x, int y) {
	int res=0;
	for (int i = 1; i <= x; i++) {
		if (x % i == 0 && y % i == 0) {
			res = i;
		}
	}
	return res;
}

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	int gcd = gcd_get(a, b);
	int lcm = (a * b) / gcd;
	printf("%d\n", gcd);
	printf("%d\n", lcm);
}

 

방법 2: 유클리드 호제법 (재귀 사용X)

두 수 A와 B의 최대공약수 = B와 r(A를 B로 나눈 나머지)의 최대공약수

즉, GCD(A,B) = GCD(B,r)

#include <stdio.h>

// 최대공약수
int gcd_get(int x, int y) {
	int r;
	while (y !=0) { // y가 0이 되면 x가 최대공약수이므로 종료
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	int gcd = gcd_get(a, b);
	int lcm = (a * b) / gcd;
	printf("%d\n", gcd);
	printf("%d\n", lcm);
}

 

방법 3: 유클리드 호제법 (재귀 사용 O)

ex> GCD(30,18) = GCD(18,12) = GCD(12,6) = GCD(6,0)

#include <stdio.h>

// 최대공약수
int gcd_get(int x, int y) {
	
	if (y == 0)return x;
	return gcd_get(y, x % y);

}

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	int gcd = gcd_get(a, b);
	int lcm = (a * b) / gcd;
	printf("%d\n", gcd);
	printf("%d\n", lcm);
}