2609 최대공약수와 최소공배수 🟫

https://www.acmicpc.net/problem/2609

---

GCD(최대 공약수)

• 최대 공약수(GCD, Greatest Common Divisor)는 두 정수의 공통된 약수 중 가장 큰 값을 의미한다.

---

유클리드 호제법

유클리드 호제법은 두 수의 최대 공약수를 효율적으로 구하는 방법 중 하나로, 반복적인 나눗셈을 통해 GCD를 구할 수 있다.

원리:

• 두 정수 a와 b(단, a > b)의 최대 공약수는 a를 b로 나눈 나머지를 r이라고 할 때, GCD(a, b) = GCD(b, r)과 같다는 원리를 이용한다.
• 나머지가 0이 될 때까지 이 과정을 반복하면, 이때의 b 값이 최대 공약수가 된다.

유클리드 호제법의 과정:

1. a를 b로 나눠 나머지 r을 구한다.
2. 나머지가 0이 아니면, a를 b로 바꾸고, b를 r로 바꾼다.
3. 나머지가 0이 될 때까지 이 과정을 반복한다.
4. 나머지가 0이 되면 그때의 b가 GCD가 된다.

알고리즘 단계:

• GCD(a, b)는 b가 0일 때, a가 최대 공약수.
• 그 외의 경우, GCD(a, b)는 GCD(b, a % b).

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static StringTokenizer st;

  public static void main(String[] args) throws IOException {
      st = new StringTokenizer(br.readLine());
      int num1 = Integer.parseInt(st.nextToken());
      int num2 = Integer.parseInt(st.nextToken());
      int result1 = gcd(num1,num2);
      int result2 = num1*num2/result1;

    bw.write(result1+"\n"+result2+"\n");
    bw.close();
    br.close();
  }

  public static int gcd(int a,int b){
    while(b!=0){
      int r = a%b;
      a=b;
      b=r;
    }
    return a;
  }
}

최소공배수는 최대공약수를 알았기 때문에 두 수의 곱 / 최대공약수를 하면 구할 수 있다.