[BOJ2609]최대공약수와 최소공배수

유클리드 호제법을 사용하면 O(logN)까지 줄일 수 있다.

 

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어떨어진다.

따라서, 최대공약수는 21이다.

 

최소 공배수는 1071*1029 / 두수의 최대 공약수 이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        int gcd = GCD(p,q);
        bw.write(gcd+"\n"+(p*q)/gcd);
        bw.close();
    }
    static int GCD(int p, int q)
    {
        if(p < q){
            int tmp = p;
            p = q;
            q = tmp;
        }
        if(q == 0)
            return p;
        return GCD(q,p%q);
    }
}