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

최대공약수와 최소공배수

2609

문제 풀이 전략

1. 두 수 (n1, n2)를 입력 받음
2. n1의 약수 중 큰 것부터 n2로 나누어지는 것을 찾음 → 가장 먼저 n2로 나눠지는 n1의 약수가 최대공약수
3. n1, n2 중 큰 수의 배수 중 작은 값부터 n1, n2 중 작은 값으로 나누었을 때 나머지가 0인 수를 찾음 → 최소공배수

코드

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

public class no_2609 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int multiple = 1; int factor = 0;

        for (int i = n1; i > 0; i--) {
            if (n1 % i == 0) {
                if (n2 % i == 0) {
                    factor = i;
                    break;
                }
            }
        }

        int large = Math.max(n1, n2);
        int small = Math.min(n1, n2);

        for (int i = 1; multiple < n1 * n2; i++) {
            multiple = large * i;
            if (multiple % small == 0) {
                break;
            }
        }

        System.out.println(factor);
        System.out.println(multiple);

        br.close();
    }
}