[GCD, LCM]최대 공약수, 최소 공배수

GCD : Greatest Common Divisor

$O(N)$

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int g = 0;
	int a = 0, b = 0;
	scanf("%d%d", &a, &b);
	for (int i = 1; i <= min(a, b); i++) {
		if (a%i == 0 && b%i == 0) {
			g = i;
		}
	}
	printf("%d\n", g);
	return 0;
}

유클리드 호제법 : 재귀

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
	if (a < b) gcd(b, a);
	if (b == 0) return a;
	else gcd(b, a%b);
}

int main() {
	int g = 0;
	int a = 0, b = 0;
	scanf("%d%d", &a, &b);
	printf("%d\n", gcd(a,b));
	return 0;
}

유클리드 호제법 : 비재귀

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
	if (a < b) gcd(b, a);
	while (b != 0) {
		int	t = a;
		a = b;
		b = t % b;
	}
	return a;
}

int main() {
	int g = 0;
	int a = 0, b = 0;
	scanf("%d%d", &a, &b);
	printf("%d\n", gcd(a,b));
	return 0;
}

N개 수의 GCD

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
	if (a < b) gcd(b, a);
	while (b != 0) {
		int	t = a;
		a = b;
		b = t % b;
	}
	return a;
}

int main() {
	int g = 0;
	int a = 0, b = 0, c = 0;
	scanf("%d%d%d", &a, &b, &c);
	printf("%d\n", gcd(gcd(a,b),c));
	return 0;
}

LCM : Least Common Multiple

1. g = 최소공배수
2. A = a*g
3. B = b*g
4. LCM = abg = A * B / g

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
	if (a < b) gcd(b, a);
	while (b != 0) {
		int	t = a;
		a = b;
		b = t % b;
	}
	return a;
}

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

int main() {
	int g = 0;
	int a = 0, b = 0;
	scanf("%d%d", &a, &b);
	printf("GCD : %d\n", gcd(a,b));
	printf("LCM : %d\n", lcm(a, b));
	return 0;
}