(C언어) 최대공약수 최소공배수 구하기 GCM LCM

#최대공약수 #최소공배수 #공약수 #GCM #LCM

 

공약수(Common Divisor)

두개 이상의 자연수 중에서 공통인 약수

 

최대공약수(GCM. Greatest Common Measure)

공약수 중에서 가장 큰 수

(예)

8의 약수: 1, 2, 4, 8

12의 약수: 1, 2, 3, 4, 6, 12

 

최소공배수(LCM. Least Common Multiple)

2개 이상의 자연수의 공통의 배수 가운데서 가장 작은 값

(예)

4의 배수: 4, 8, 12, 16, 20, ...

6의 배수는: 6, 12, 18, 24, 30, ...

 

 

다음 코드는 C언어를 이용해서 최대공약수와 최소공배수를 구하는 프로그램입니다.

#define _CRT_SECURE_NO_WARNINGS   // Visual Studio

#include <stdio.h>
int main()
{
	int a, b;
	int big, small, m, g, gcm, lcm; // 큰값, 작은값, 몫, 나머지, 최대공약수, 최소공배수

	printf("두 정수를 입력하세요: ");
	scanf("%d %d", &a, &b);

	// 큰 수를 big, 작은수를 small에 저장
	if (a > b)
	{
		big = a;
		small = b;
	}
	else
	{
		big = b;
		small = a;
	}

	while (1)
	{
		m = big / small;	// 큰수를 작은 수로 나눈 몫 
		g = big % small;	// 큰수를 작은 수로 나눈 나머지 

		if (g == 0) break;

		big = small;
		small = g;
	}
	gcm = small;
	lcm = (a * b) / gcm;

	printf("최대공약수(GCM) = %d\n", gcm);
	printf("최소공배수(LCM) = %d\n", lcm);

	return 0;
}

(Output)