[C/C++] 최대공약수(GCD), 최소공배수(LCM) (유클리드 호제법)

 

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

• a, b : 최대공약수를 구하고자 하는 두 수
• r : a를 b로 나눈 나머지 = ( a%b ) = ( a mod b )
• 식 : GCD(a,b) = GCD(b, r)

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

만약에 a = 10, b= 6 이라고 한다면

GCD(10, 6) => return GCD(6, 4)

GCD(6, 4) => return GDC(4, 2)

GCD(4, 2) => return GDC(2, 0)

GDC(2, 0) => return 2

 

최소공배수 공식(최대공약수를 이용)a,b : 최소공배수를 구하고자 하는 두 수

• GCD(a,b) : a와b의 최대공약수
• (최소공배수 * 최대공약수 = a * b)를 이용
• 식 : a * b / GCD(a,b)

int LCM(int a, int b) 
{
	return a * b / GCD(a, b);
}

만약에 a = 10, b= 6 이라고 한다면

LCM(10, 6) => return 10 * 6 / 2 = 30

 

 

<실행 결과>

#include<stdio.h>
#include<algorithm>


int GCD(int a, int b) // 최대공약수
{
	if (b == 0) {
		return a;
	}
	else {
		return GCD(b, a % b);
	}
}

int LCM(int a, int b) // 최소공배수
{
	return a * b / GCD(a, b);
}

int main(void)
{
	printf("  최대공약수= %d\n  최소공배수= %d \n", GCD(6, 10), LCM(6, 10) );
}