[java] 2609번 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

package backjoon_2609;
import java.io.*;
import java.util.StringTokenizer;
import java.math.*;
public class Main {
 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int num1 = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());
        int gcd =0;
        int lcm =0;
        for(int i = 1; i<=num1 && i <= num2; i++) {
            if(num1 % i ==0 && num2 % i ==0) {
                gcd =i;
            }
        }
        for(int i = Math.max(num1,num2); i<=num1*num2; i++) {
            if(i%num1 == 0 && i % num2 ==0) {
                lcm = i;
                break;
            }
        }
        System.out.println(gcd);
        System.out.println(lcm);
    }
}
 

 

최소공배수는 공톤된 배수를 찾는 문제고, 최대공약수는 공톤된 약수를 찾는 것이 관건이다. 그래서 두 개 모두 for문을 돌려서 나머지 연산을 했을 때 나누어 떨어지는 것을 찾는다. 최대 공약수는 가장 작은 수부터 시작하여 계산한다. 그래서 만약 같은 것이 나오면 i로 바꿔준다. 이걸 반복하면 나중에는 공약수 중 가장 큰 수가 나오게 된다.

최소 공배수는 가장 큰 것부터 시작하게 된다. 두 수를 곱한 것이 최소 공배수중 가장 큰 수일 것이다. 이렇게 세팅해두고 두 수가 나누어 떨어지는 것을 계산하면 된다. 최소 공배수를 찾게되면 break;를 걸어야한다. 만약 걸지 않으면 최소가 아니라 그냥 공배수를 출력하게 된다.