C언어 18제] C언어 콘서트 CHAPTER 6 p233 도전문제

출처 : 반크(독도 포스터)

 

도전문제]

약수 구하기 프로그램을 참조하여서 두 수의 최대 공약수를 구하는 프로그램을 작성해보자.

일반적인 방법도 있고 유클리드의 방법도 있다. 

 

참고풀이]

//Dev-C++ 5.11에서 작업함.
#include <stdio.h> 

int main()
{
   int num1, num2;//두 수 입력변수
   int min;//반복의 끝수변수 
   int na;//두수의 공통약수
   int chk;//공통약수가 있는 지 체크변수 
   int GCD;//최대공약수 

   //두 수를 입력받는다.
   printf("첫번째 정수를 입력하시오 : ");
   scanf("%d",&num1);
   printf("두번째 정수를 입력하시오 : ");
   scanf("%d",&num2);

   //일반적인 방법인 두 수의 공통 약수들을 곱하여 최대공약수를 구한다. 
   printf("%d와 %d의 ",num1,num2);
   GCD=1;
   while(1)
   {
      chk=1;
      if(num1>num2) min=num2; else min=num1;
      for(na=2;na<min;na++)
         if(num1%na==0 && num2%na==0)
         {
            GCD*=na;
            num1/=na;
            num2/=na;
            chk=0;
            break;
         }
      if(chk) break;
   }

   //결과출력
   if(GCD==1) printf("두 수는 서로소입니다.\n그러므로 최대공약수는 %d입니다.\n",GCD);
   else printf("최대공약수는 %d입니다.\n",GCD);

   return 0;
}

 

 

참고풀이 결과]

 

 

 

 

대한민국의 아름다운 영토, 독도의 봄