최대공약수/최소공배수

문제 : 두 수를 입력받아 최대공약수/최소공배수를 구하는 gcdlcm 함수를 구현하시오.

---

[정리]

1. 공약수(greatest common divisor) : N 개의 수가 있을 때, N 개 모두를 나머지 없이(0) 나눌 수 있는 수

2. 공배수(least common multiple) : N 개의 수가 있을 때, N 개 모두의 배수가 되는 수

[예]

ex) 10과 20의 공약수는 1, 2, 5, 10

ex)  2와 3의 공배수는 6, 12, 18, ...

#최대공약수/최소공배수 알고리즘 - Programmers 참조

public int[] gcdlcm(int a, int b) {
    int[] answer = new int[2];
 
    answer[0] = gcd(a,b);
    answer[1] = (a*b)/answer[0];
 
    return answer;
}
 
public static int gcd(int p, int q)
{
    if (q == 0) return p;
    return gcd(q, p%q);
}

+ 재귀함수를 이용

+ 나머지를 이용하여 큰 수와 작은 수의 위치를 변경 (Good)

+ 최소공배수 공식 : (a * b) / gcd

: 72, 98의 최대공약수, 최소공배수

1. gcd(72, 98)

2. gcd(98, 72) - 여기서 큰 수와 작은 수의 위치가 변경됨.

3. gcd(72, 26)

4. gcd(26, 20)

5. gcd(20, 6)

6. gcd(6, 2)

7. gcd(2, 0) -> return 2

8. 72 * 98 / 2 = 3528

: 11, 12의 최대공약수, 최소공배수

1. gcd(11, 12)

2. gcd(12, 11)

3. gcd(11, 1)

4. gcd(1, 0) -> return 1

5. 11 * 12 / 1 = 132