GCD(Greatest Common Divisor), LCM(Least Common Multiple )

최대공약수 ,GCD(Greatest Common Divisor)

: 두 자연수가 공통으로 갖는 약수들 중에서 가장 큰 값

 

최소공배수, LCM(Least Common <Multiple)

: 두 자연수들의 배수들 중에서 공통된 가장 작은 수

LCM = 두 자연수의 곱 / GCD

 

유클리드 호제법(Euclidean Algorithm)

: 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면(전제조건 : a > b)

 a와 b의 최대공약수 ==  b와 r의 최대공약수

이러한 성질을 이용하여 b를 r로 나눈 나머지 r'를 구하고 이러한 과정을 반복하여 나머지 r'가 0되었을때 나누는 수가

a와 b의 최대공약수이다. 

 

하단 코드 내 Euclidean함수의 if(b == 0)은

나머지 r' == 0인 경우, 나누는 값을 리턴함으로써 최대공약수를 return하고 있다.

 

또한 재귀함수(recursive function)을 이용하여 나머지 값을 b인자(나누는 인자)로 받고 있으며

이는 그 다음번에는 나눠지는 인자로 들어간다. 

 

중간에 a > b인 전제조건을 충족시키기 위한 temp인자가 만들어진다. 

#include <stdio.h>
int Euclidean(int a, int b)
{
    if (b == 0) return a;
    else return Euclidean(b, a%b);
}
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    
    if( a < b )
    {
    	int temp = a;
        a = b;
        b = temp;
    }
    
    int GCD = Euclidean(a, b);
    int LCM = a * b / GCD;
    printf("GCD : %d, LCM: %d\n", GCD, LCM);

}

 

+) return b ? Euclidean_short(b, a % b) 로 구현 가능

 

gcd 코드는 ternary conditional operator를 이용한 숏코딩가능하다.

형태  :  condition ? value_if_true : value_if_false

 ex. return b ? Euclidean_short(b, a % b) :

b가  true라면 즉, non-zero인 경우 ? 다음에 위치한 값(gcd(b, a % b))을 값는다.

또는 false인 경우 즉, b 가 0인 경우 a를 갖는다.

이러한 statement를 return값으로 가지기 때문에 변수로 저장되는 것이 아닌 최종 값이 바로 return하게 된다 .

따라서 보다 간결한 코드를 작성할 수 있다. 

int Euclidean(int a, int b)
{
    if (b == 0) return a;
    else return Euclidean(b, a%b);
}

int Euclidean_short(int a, int b)
{
	return b ? Euclidean_short(b, a % b) : a;
}