두 개의 정수를 입력받아서 최대 공약수(GCM)를 구하는 프로그램을 작성해 보자.

#include <stdio.h>


int gcm(int a, int b);


int main(void)
{
      int val1, val2;


      printf("두 개의 정수 입력 : ");
      scanf("%d %d", &val1, &val2);


      printf("G C M : %d\n", gcm(val1, val2));


      return 0;
}


int gcm(int a, int b)
{
      int g;


      for(g=(a<b)? a:b; ; g--)
            if(a%g==0 && b%g==0)
                  return g;
}

유클리드 호제법을 이용해서 문제를 풀어보자.

#include <stdio.h>


int gcm(int a, int b);


int main(void)
{
      int val1, val2;


      printf("두 개의 정수 입력 : ");
      scanf("%d %d", &val1, &val2);


      printf("G C M : %d\n", gcm(val1, val2));


      return 0;
}


int gcm(int a, int b)
{
      int r=1;


      do
      {
            r=a%b;
            a=b;
            b=r;
      }while(r!=0);


      return a;
}

신고

+ Recent posts

티스토리 툴바