최대 공약수, 최소 공배수 구하기

문제).

두 정수의 최대 공약수 및 최소 공배수를 구하는 함수를 만드시오.

 

답은 아래에... ↓

 

 

---

 

 

 

 

 

스스로 풀어보시고... ↓

 

 

 

 

 

 

---

 

 

 

 

아래 답과 비교해보세요. ↓

 

 

 

 

 

---

1. 최대공약수(Greatest Common Divisor) - looping으로 풀기

/* 
* 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘을 활용한 
* 최대 공약수 계산하는 함수
*/
int GDC(int x, int y)
{
    int tmp;

    while(y != 0) {
        tmp = x % y;
        x = y;
        y = tmp;
    }
    return x;
}

 

2. 최대공약수(Greatest Common Divisor) - 재귀호출함수로 풀기

/* 
* 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘을 활용한 
* 최대 공약수 계산하는 함수
*/
int GDC(int x, int y)
{
    if(y == 0) {
        return x;
    }
    return GDC(y, x % y);
}

 

3. 최소 공배수 (Least Common Mulitple)

/* 
* least common multiple
*/
int LCM(int x, int y)
{
	return x * y / GCD(x, y);
}