[java 백준] 실버 5/ 2609번 최대공약수와 최소공배수

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

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Integer.parseInt(st.nextToken());
        long b = Integer.parseInt(st.nextToken());
        if (a > b) {
            long ans1 = gcd(a, b);
            long ans2 = a / ans1;
            long ans3 = b / ans1;
            System.out.println(ans1);
            System.out.println(ans1 * ans2 * ans3);
        } else if (a < b) {
            long ans1 = gcd(b, a);
            long ans2 = a / ans1;
            long ans3 = b / ans1;
            System.out.println(ans1);
            System.out.println(ans1 * ans2 * ans3);
        } else if (a == b) {
            
            System.out.println(a);
            System.out.println(a);
        }
 
    }
 
}

 

유클리드 호제법을 이용해서 풀면된다.

잊지말자 최대공약수는 유클리드 호제법..!!!!