[백준] 1934번 최소공배수 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
17. 정수론 및 조합론
정수론과 조합론을 배워 봅시다.
정수론과 조합론을 배워 봅시다.
Java / Python
4. 최소공배수
유클리드 알고리즘으로 더 빠르게 푸는 문제
두 개의 자연수를 입력받아 최소 공배수를 출력하는 문제로, 유클리드 알고리즘을 이용하는 문제입니다.
유클리드 호제법 (Euclidean algorithm)이란
2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이며, 정리는 다음과 같습니다.
- Java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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;
while(T-- > 0){
st = new StringTokenizer(br.readLine(), " ");
int number1 = Integer.parseInt(st.nextToken());
int number2 = Integer.parseInt(st.nextToken());
int result1 = gcd(number1, number2);
System.out.println(number1 * number2 / result1);
}
}
public static int gcd(int n1, int n2){ // 최대 공약수
if(n2 == 0) return n1;
return gcd(n2, n1 % n2);
}
}
- Python
import sys
T = int(sys.stdin.readline())
# gcd
def gcd(n1, n2):
if n2 == 0 :
return n1
else :
return gcd(n2, n1 % n2)
while T > 0 :
num1, num2 = map(int, sys.stdin.readline().split())
result = gcd(num1, num2)
# 최소공배수
print(num1 * num2 // result)
T -= 1
Author And Source
이 문제에 관하여([백준] 1934번 최소공배수 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-1934번-최소공배수-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)