[C언어] C언어 최대 공약수 구하기 알고리즘 예제 (재귀함수 최대공약수)

아래 코드는 두 수의 최대공약수를 구해주는 함수에 관한 코드이다.

/*
	최대공약수 구하기 알고리즘
	2개 값 입력, 최대 공약수 출력 함수
	알고리즘:
		1. v가 u보다 크면 v와 u값을 바꾼다.
		2. u = u - v
		3. u가 0이면 v가 최대공약수. 아니면 다시 처음으로 돌아간다.
*/

#include<stdio.h>

int GCD(void) {
	int u = 0;
	int v = 0;
	int temp = 0;
	int result = 0;

	printf("2개의 값을 입력하시오.\n");
	printf("a:");
	scanf_s("%d", &u);
	printf("b:");
	scanf_s("%d", &v);

	while(1)
	{
		if (v > u) {
			temp = u;
			u = v;			// 1. v가 u보다 크다면, v와 u값을 바꾼다.
			v = temp;

			u = u - v;		// 2. 
		}
		else {
			u = u - v;
		}

		if (u == 0)
		{
			result = v;		// 3. u가 0이면 v가 최대공약수
			break;
		}
	}
	return result;
}

int main(void)
{
	int result;
	result = GCD();
	printf("최대공약수는: %d", result);

	return 0;
}

 

반응형

 

똑같은 기능을 하는 최대 공약수를 구하는 방법을 아래는 재귀함수를 이용한 방식이다.

/*
	최대공약수 구하기 알고리즘(Recursive Function 모드 (재귀함수))
	2개 값 입력, 최대 공약수 출력 함수
	알고리즘:
		1. v가 0이 아니면,
			1.1. u = u % v
			1.2. u와 v를 교환
			1.3. 1으로 돌아감.
		2. v가 0이면 u가 최대공약수
*/

#include<stdio.h>

int GCD_recursion(int u, int v) {
	
	if (v == 0)
		return u;
	else
		return GCD_recursion(v, u % v);
}

int main(void)
{
	int u, v, result;
	
	printf("2개의 값을 입력하시오.\n");
	printf("a:");
	scanf_s("%d", &u);
	printf("b:");
	scanf_s("%d", &v);

	result = GCD_recursion(u, v);
	printf("최대공약수는: %d", result);

	return 0;
}

 

아래 함수는 똑같이 최대 공약수를 구하는 방법이지만, 알고리즘 성능이 좀 더 향상 된 방법이다.

/*
	최대공약수 구하기 알고리즘(성능 개선 모드)
	2개 값 입력, 최대 공약수 출력 함수
	알고리즘:
		1. v가 0이 아니면,
			1.1. u = u % v
			1.2. u와 v를 교환
			1.3. 1으로 돌아감.
		2. v가 0이면 u가 최대공약수
*/

#include<stdio.h>

int GCD(void) {
	int u = 0;
	int v = 0;
	int temp = 0;
	int result = 0;

	printf("2개의 값을 입력하시오.\n");
	printf("a:");
	scanf_s("%d", &u);
	printf("b:");
	scanf_s("%d", &v);

	while(v != 0)	// v가 0이 아니면 무한 반복
	{
		u = u % v;	// 1.1.
		temp = v;	// 1.2.
		v = u;
		u = temp;
	}
	result = u;		// 2.

	return result;
}

int main(void)
{
	int result;
	result = GCD();
	printf("최대공약수는: %d", result);

	return 0;
}