c언어 - 유클리드 알고리즘

유클리드 알고리즘이란?

- 두 양의 정수들에 대한 최대 공약수를 찾아내기 위한 알고리듬

등식 : gcd(a,b) = gcd(b,a mod b)

 

ex)

gcd(44, 12)=gcd(12, 8)
= gcd(8,4)
= gcd(4,0)
= 4

44와 12의 최대 공약수 -> 4

 

c언어 소스

 

#include <stdio.h>
#include <math.h>

int Euclid(int num1, int num2);

int main()
{
 int num1, num2, gcd;

 printf("두 정수를 입력하세요 : ");
 scanf("%d %d", &num1, &num2);

 if(num1 > num2)
  gcd = Euclid(abs(num1), abs(num2)); //절댓값으로 넣음
 else
  gcd = Euclid(abs(num2), abs(num1));

 printf("%d, %d의 최대 공약수 : %d \n", num1, num2, gcd);

 return 0;
}

int Euclid(int num1, int num2)
{
 int r; //나머지

 while(num2)
 {
  r = num1%num2;
  num1 = num2;
  num2 = r;
 }

 return num1; //gcd(x, 0)의 상태
}

 

 

실행 결과