[GCD 알고리즘] Euclidean Algorithm

1. 유클리드 알고리즘이란?

Euclidean Algorithm (유클리드 호제법이라고도 합니다)은 두 수의 GCD(Greatest Common Divisor 최대공약수)를 구하는 알고리즘입니다. 

 

2. 원리

   STEP 1: 두 자연수 A, B가 있을때 A > B라 가정

   STEP 2: A를 B로 나눈 나머지를 C라 가정.

   STEP 3: C가 0이면 B는 GCD

   STEP 4: C가 0이 아니면 B값을 A에 대입하고 C값을 B에 대입해 STEP 2부터 반복.

 

1.  A = 12   B = 18
   1. A와 B를 나눈 나머지C는 12
   2. B 가 0이 아니므로 B = A,  C = B 대입
2.  A = 18   B = 12
   1. A와 B를 나눈 나머지C는 6
   2. B 가 0이 아니므로 B = A,  C = B 대입
3.  A = 12   B = 6
   1. A와 B를 나눈 나머지C는 6
   2. B 가 0이 아니므로 B = A,  C = B 대입
4.  A = 6   B = 0
   1. B가 0이니 GCD은 A

 

 

3. C언어로 알고리즘 구현

int getGCD(int A, int B)
{
    if (B == 0)
        return A;
    else
        return getGCD(B, A % B);
}

 

 

 

 

 

본 게시물은 제가 공부한 내용을 올린 글이라 내용이 틀리거나 오류가 있을 수도 있습니다. 만약 그럴 시 jaewonahn1234@gmail.com으로 피드백해주시면 감사하겠습니다