최대공약수 구하기 (feat. 유클리드 호제법)

내 코드

int main(void)
{
	int num1, num2;
	int bigger;
	printf(" 두 수 입력 : ");
	scanf("%d %d", &num1, &num2);
	bigger = num1 > num2 ? num1 : num2;

	int i = 1;
	int max;
	printf("%d와 %d의 공약수는 \n", num1, num2);
	while (bigger)
	{
		if (num1 % i == 0 && num2 % i == 0)
		{
		printf("%d\n", i);
		max = i;
		}
		i++;
		bigger--;
	}
	printf("최대 공약수는 : %d", max);
	return 0;
}

많이 난잡하다.

스토리 올리면서 생각했는데 bigger 숫자로 돌리는게 아니라 smaller 숫자로 해야하는구나

 

수정1

int main(void)
{
	int num1, num2;
	int smaller;
	printf(" 두 수 입력 : ");
	scanf("%d %d", &num1, &num2);
	smaller = num1 < num2 ? num1 : num2;

	int i = 1;
	int max;
	printf("%d와 %d의 공약수는 \n", num1, num2);
	while (smaller)
	{
		if (num1 % i == 0 && num2 % i == 0)
		{
		printf("%d\n", i);
		max = i;
		}
		i++;
		smaller--;
	}
	printf("최대 공약수는 : %d", max);
	return 0;
}

 

 

유클리드 호제법이라고 있다고 한다.

최대공약수를 구하는 알고리즘이라는데

 

C코드 #1 

재귀함수

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

C코드 #2

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