[C프로그래밍]최대공약수 구하기(Great common divisor,GCD)

 

 

 

 

1.

#include <stdio.h>

int main()
{
	int m,n,T;
	
	printf("두 개의 정수를 입력하라\n");
	scanf("%d%d",&m,&n);
	
	if(m<n) T=m;
	else T=n;
	
	while (!(m%T==0 && n%T==0))  //  while (m%T!=0 || n%T!=0)과 같음
		T=T-1;
		
	printf("%d와 %d의 최대 공약수는 %d이다\n",m,n,T);
 	return 0;
}

 

추가문제 : 세 정수의 최대 공약수를 구하는 알고리즘을 제시하고 c코딩하라

예를 들어 세 정수가 12,18,66이라면 답은 6이다.

 

- 세 수를 정렬하는 알고리즘을 짠뒤, 최대 공약수를 구하는 알고리즘을 구현하였음. 

 

 

 

2, 유클리드 호제법