0%

[백준/2609] 최대공약수와 최소공배수

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2609

Review

  • 최대공약수(GCD) 구하기: A B 중 큰 수, 작은 수 판별한 다음 큰 수를 작은 수로 나누어 나머지를 구한다. 그리고 나눈 나머지가 0이면 작은 수가 최대공약수, 나머지가 0이 아니면 나누기를 반복하면 된다.
  • 최소공배수(LCM) 구하기: A * B / GCD

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  
  public static int GCD(int a, int b) {
    if(a % b == 0) {
      return b;
    } else {
      return GCD(b, a % b);
    }
  }
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String[] line = bf.readLine().split(" ");
    int A = Integer.parseInt(line[0]);
    int B = Integer.parseInt(line[1]);
    
    int gcd = A > B ? GCD(A, B) : GCD(B, A);
    int lcm = A * B / gcd;
    System.out.println(gcd);
    System.out.println(lcm);
  }
  
}