[BAEJOON] 1934 최소공배수

문제 요약

• 알고리즘 분류: 유클리드 호제법
• 난이도: Bronze1
• 문제내용:
  • 테스트케이스 개수만큼 두 수의 최소 공배수를 구하면 된다.
• 사이트: https://www.acmicpc.net/problem/1934

1934번: 최소공배수

문제풀이

1. 위 문제는 유클리드 호제법으로 푸는 방법이다. 유클리드 호제법에 내한 내용은 아래의 사이트에 참조 하면된다

[알고리즘/이론] - 유클리드 호제법(Euclidean algorithm)

유클리드 호제법(Euclidean algorithm)

 

CODE

Python

import sys
input = sys.stdin.readline

def Euclid(x, y):
    print(x, y)
    if x % y == 0:
        return y
    return Euclid(y, x % y)

for _ in range(int(input())):
    A, B = map(int, input().split())
    print(A * B // Euclid(A, B))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int A, B;
		for(int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			System.out.println(A * B / Euclid(A, B));
						
		}
		
	}
	
	public static int Euclid(int x, int y) {
		if (x % y == 0) {
			return y;
		}else {
			return Euclid(y, x % y);
		}
		
	}
	
}