https://programmers.co.kr/learn/courses/30/lessons/12940

소스

1
2
3
4
5
6
7
8
9
10
11
12
public int[] solution(int n, int m) {
    int big = n > m ? n : m;
    int small = n < m ? n : m;
    
    while (m != 0) {
        int r = n % m;
        n = m;
        m = r;
    }
    
    return new int[] {n, n * (big / n) * (small / n)};
}

흐름

  • 유클리드 호제법으로 처리

    두 양의 정수 $$ a, b (a > b) $$ 에 대하여 $$ a = bq + r(0 ≤ r < a) $$
    라 하면, a, b 의 최대공약수는 b, r의 최대공약수와 같다.

  1. 두 수를 중 큰 수와 작은 수 구분

  2. 큰 수 a의 최대공약수는 b와 r(a mod b)의 최대 공약수와 같으므로 작은 수 m이 0이 될 때 까지 반복

  3. 최소공배수는 최대공약수(G) * (a / G) * (m / G) 이므로 계산해서 배열에 할당한다.

    • $$ (a * b) / G $$ 로 하면 수가 큰 경우 overflow가 발생 할 가능성이 있음.

  4. 끝

유클리드 호제법

두 양의 정수 $$ A, B (A > B) $$ 에 대하여 $$ A = Bq + R(0 ≤ R < a) $$
라 하면, A, B 의 최대공약수는 B, R의 최대공약수와 같다.

이 때 R은 A mod B 한 값으로 식으로 나타내면 아래와 같다.

$$ G(A,B) = G(B,R) $$

A와 B에게 최대공약수 G가 있다면,

$$ A = aG, B = bG $$

과 같이 나타 낼수 있고 이 때 a와 b는 반드시 서로소 여야 한다.
위에서 A mod B 한 값이 R 이라고 정의했고 A와 B를 나눈 값을 q라고 한다면,

$$ A = Bq + R $$
$$ aG = bGq + R $$
$$ R = G(a-bq) $$

처럼 전개 될 수 있고, 이 경우 R과 B가 G 라는 최대 공약수를 갖기 떄문에 $$ a-bq $$ 와 b가 서로소 임을 증명하면 된다.

만약 $$ a-bq $$ 와 b가 서로소가 아니라면, 둘은 공약수가 존재 하기 떄문에 아래와 같이 표현 할 수 있다.

$$ a-bq = pm , b = pn $$
$$ a = bq + pm $$
$$ a = pnq + pm $$
$$ a = p(nq + m), b = pn $$

이 때 a와 b는 서로소인데 p 라는 공약수를 갖게 되므로
a와 b가 서로소라는 전제가 모순되어 $$ a-bq $$ 와 b는 서로소임이 증명되고 B와 R의 최대 공약수가 G 인 것이 된다.

참고 사이트