(BOJ/JAVA) 백준 1934: 최소공배수(자바)

문제 정보

문제 이름 – 최소 공배수
어려움 – 브론즈 I
문제 번호 – 1934호

---

문제 연결

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

1934: 최소공배수

두 자연수 A와 B에 대해 A의 배수이면서 동시에 B의 배수인 자연수를 A와 B의 공배수라고 합니다. 이러한 공배수 중 가장 작은 것을 최소 공배수라고 합니다. 예를 들어, 6과 15의 공배수는 30, 60, 90 등입니다.

www.acmicpc.net

---

문제

두 자연수 A와 B에 대해 A의 배수이면서 동시에 B의 배수인 자연수를 A와 B의 공배수라고 합니다. 이러한 공배수 중 가장 작은 것을 최소 공배수라고 합니다. 예를 들어, 6과 15의 공배수는 30, 60, 90 등이고 최소 공배수는 30입니다.
두 자연수 A와 B가 주어졌을 때 A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

---

기입

테스트 케이스의 수 T(1 ≤ T ≤ 1,000)는 첫 번째 줄에 표시됩니다. A와 B는 두 번째 줄부터 T 줄로 주어집니다. (1 ≤ A, B ≤ 45,000)

---

누르다

A와 B의 최소 공배수를 입력한 순서대로 첫 줄부터 시작하여 한 줄에 하나씩 T 줄에 인쇄합니다.

---

예제 입력/출력

예제 입력	샘플 출력
3 1 45000 6 10 13 17	45000 30 221

---

알고리즘 분류

● 수학
● 정수론
● 유클리드 알고리즘

---

소스 코드

package Lv1_Bronze;

import java.io.*;
import java.util.*;
/**
 * @author HanHoon
 * @category 수학, 정수론, 유클리드 호제법
 * https://www.acmicpc.net/problem/1934
 */
public class BOJ_B1_1934_최소공배수 {
    // 유클리드 호제법
    public static long gcd(long a, long b){
        if(a < b){
            long tmp = a;
            a = b;
            b = tmp;
        }
        if(b==0)
            return a;
        return gcd(b, a%b);
    }
    public static void main(String() args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder str = new StringBuilder();

        // T: 테스트 케이스 개수
        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            str.append(A*B/gcd(A,B)).append("\n");
        }
        System.out.print(str);
        br.close();
    }
}

---

백준 목록

백준 목록

BOJ 런칭!! ● (BOJ) 백준 회원가입 및 시작 방법 ● (BOJ) Solved.AC 평가(Tier) 및 적용 ● (BOJ/JAVA) 백준 소스코드 제출 시 주의사항(Java) Bronze ● Bronze V – ● Bronze IV – ● 브론즈 III -..

한훈.tistory.com

---

준비된 자에게 기회는 찾아옵니다.

---