2623 : 최대공약수 구하기

문제 설명

두 정수 a, b를 입력받아서, a, b의 최대공약수를 출력하시오.

입력

정수 a, b가 공백으로 구분되어 입력된다. (1<=a, b<=10,000)

출력

a, b의 최대공약수를 출력한다.

입력 예시

64 128

출력 예시

64

최대공약수 구하기 문제.

'유클리드 호제법'이라고 널리 알려진 최대공약수를 구하는 알고리즘이 있다.

/*유클리드 호제법

 : 두 양의 정수 a, b (b>a)에 대하여 b = aq + r (0<=r<a)라 하면, a, b의 최대공약수는 a,r의 최대공약수와 같다. */

인터넷에서 찾아보니 예시 코드들을 찾아볼 수 있었다.

예제 1)

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

/* 출처

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95 */

예제 2)

#include <stdio.h>

int max(int a,int b);

int main (void)

{

int a,b;

printf("두 수를 입력 하시오");

printf("\n");

scanf("%d%d",&a,&b);

if(a>=b) 

  {

printf("\n");

printf("두 수의 최대공약수 : %d\n",max(a,b));

}

else

  {

printf("\n");

printf("두 수의 최대공약수 : %d\n",max(b,a));

}

}

int max(int a,int b)

{

if(a%b==0) return b; 

else return max(b,a%b);

}

/* 출처

https://m.blog.naver.com/PostView.nhn?blogId=raraduck&logNo=90177228431&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F */

찾아보니 상당히 많은 예시 코드들이 재귀함수로 이루어져 있었다.

재귀함수는 컴퓨터에 무리가 가므로 되도록 사용하지 않는것이 좋다는 얘기를 들어서

재귀함수 없이 유클리드 호제법을 이용한 코드를 짜보았다.

#include <stdio.h>

int main(void)

{

int a,b,t;

scanf("%d %d",&a,&b);

while(a%b!=0)

{

  t=b;

  b=a%b;

  a=t;

}

printf("%d",b);

return 0;

}

/* 참고 자료

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm */