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

[Bronze I] 최대공약수와 최소공배수 - 2609

문제 링크

성능 요약

메모리: 16212 KB, 시간: 152 ms

분류

유클리드 호제법(euclidean), 수학(math), 정수론(number_theory)

문제 설명

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

입력

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

출력

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

아이디어

• 최대공약수 구하기
  • i를 1부터 n까지 for문을 이용하여 1씩 증가시키며 나누어 떨어지는지 검사한다.
  • loop의 수를 줄이기 위해 두 숫자 중 더 작은 숫자를 넘기 전까지만 수행한다.(최대공약수는 작은 수보다 더 클 수 없음)
• 최소공배수
  • 두 수의 곱 나누기 최대공약수

답안코드

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

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));

        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        
        int x = Integer.parseInt(st.nextToken().toString());
        int y = Integer.parseInt(st.nextToken().toString());

        int max = 1;    // 최대공약수
        for (int i = 1; i <= x && i <= y; i++) {
            if (x % i == 0 && y % i == 0) {
                if (i > max) max = i;
            }
        }
        
        int min = (x * y) / max;    // 최소 공배수
        bw.write(max + "\n" + min);

        bw.flush();
        bw.close();
    }
}

BOJ 카테고리 내 다른 글 보러가기