최대공약수(GCD), 최소공배수(LCM)

최대공약수 공식(유클리드 호제법) 

• 두 수 a, b
• r : a % b = a mod b
• gcd(a,b) = gcd(b, a % b) = gcd(b, r)

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

int gcd(int a, int b) {
	int r;
	while (b) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

 

 

 

최소공배수 공식 (최대공약수 활용)

• 최소공배수 * 최대 공약수 = a * b
• 최소공배수 = a*b / gcd(a,b)

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

int gcd(int a, int b) {
	int r;
	while (b) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

 

 

 

관련 문제 백준 장미 BOJ 3343