공약수 - 2436번

---

풀이 방법

유클리드 호제법 

최소 공배수 = 두 자연수의 곱 / 최대 공약수

 

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static long A, B;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());

        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i * i < B; i++) {
            if (B % i == 0) {
                list.add(i);
                list.add((int) (B / i));
            }
        }

        int[] answer = {0, 0};

        long max = Long.MAX_VALUE;

        for (int i = 0; i < list.size(); i++) {
            for (int j = i; j < list.size(); j++) {
                long x = list.get(i);
                long y = list.get(j);
                long z = cal((int) x, (int) y);
                if (z == A && x + y < max && (x * y) / z == B) {
                    answer[0] = (int) x;
                    answer[1] = (int) y;
                    max = x + y;
                }
            }
        }
        Arrays.sort(answer);

        System.out.println(answer[0] + " " + answer[1]);
    }

    static int cal(int a, int b) {
        if (b % a == 0) {
            return a;
        } else {
            return cal(b % a, a);
        }
    }
}