[알고리즘]최소공배수와 최대공약수, 유클리드 호제

최소공배수 - lcm(a,b) or [a,b]로 표기한다.
  - 공배수란, 두수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다.
  - 그러므로 최소공배수는 공배수 중에서 가장 작은 수를 뜻한다.

예시로,
  10 : 10, 20, 30, 40, 50, 60, 70, ....
  12 : 12, 24, 36, 48, 60, 72......

  일때 공배수 중에 가장 작은 수인 60이 최소공배수가 된다.

숫자로 나열하는게 힘들다면, 소인수분해를 사용해 찾을 수 있다.
  10 = 2x5
  12 = 2^2x3
중복되는 소인수의 차수가 큰 횟수만큼,
나머지 소인수를 모두 곱해주주면
 -> 그 값이 최소공배수!

즉, 2를 두 번, 3을 한 번, 그리고 5를 한 번 곱한 값 -> 60.

최대공약수 - gcd(a,b) or (a,b)로 표기한다.
 - 공약수란, 두수, 혹인 그 이상의 여러 수의 공통인 약수라는 뜻이다.
 - 그러므로 최대공약수는 공양수 중에서 가장 큰 것.

예시로,
  12 : 1, 2, 3, 4, 6, 12
  18 : 1, 2, 3, 6, 9 ,18

  일때 모두 같이 있는 숫자가 공약수가 된다.
  즉 이 경우에는 1, 2, 3, 6이 공약수!
  최대공약수는 찾은 공약수 중에 가장 큰 6이 된다.

유클리드 호제법
  - 2015, 246과 같이 두 수의 약수를 찾는게 어려울 때, 사용하자.

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

 - 예제로
    72와 40의 최대공약수를 유클리드 호제법을 이용해 구해보자.
    72>40
    72=40x1+32
    40=32x1+8
    32=8*4+0

    나머지가 0이 되기 바로 직전 연산의 나머지가 원래 두 수의 최대공약수가 된다.
    즉, 8.

[JAVA 구현코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Quiz_2609 {
 
    public static void main(String[]args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
 
        int bigger = Math.max(A,B);
        int smaller = Math.min(A,B);
        int gcm = gcm(bigger, smaller);
        int lcm = A*B/gcm;
        System.out.println(gcm);
        System.out.println(lcm);
 
 
    }
    public static int gcm(int big, int small){
        while(small>0){
            int r=big%small;//나머지
            big=small;
            small=r;
 
        }
        return big;
    }
 
}