BOJ 2609 - 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수 (acmicpc.net)

2609번: 최대공약수와 최소공배수

 

---

 

두 수 n1 과 n2(n1<n2) 가 있을 때

 

n1과 n2를 0으로 나눌 수있는 1 이상의 수 중 가장 큰 수를 최대공약수라 한다.

최소공배수는 n1*n2 를 한 값에 최대공약수를 나누면 쉽게 구할 수 있다.

 

바로 코드를 보자

 

 

 

 

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

/**
 * https://www.acmicpc.net/problem/2609
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());

        int gcd = 0; // 최대공약수

        int min = Math.min(n1, n2);

        for (int i = min; i >=1; i--) {
            if (n1 % i == 0 && n2 % i == 0) {
                gcd = i;
                break;
            }
        }

        sb.append(gcd).append("\n").append(n1 * n2 / gcd);
        System.out.println(sb);
    }
}