728x90
문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
두 개의 정수가 주어졌을 때, 최대공약수와 최소공배수를 구하는 프로그램을 작성하세요.
입력 예시
50 10
출력 예시
10 50
코드
첫 번째 줄에 두 개의 정수가 공백을 사이에 두고 주어집니다.
- 1 ≤ 주어지는 정수 ≤ 10,000
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));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 두 수의 최대공약수
int gcd = gcd(Math.max(a, b), Math.min(a, b));
// 두 수의 최소 공배수
int lcm = a * b / gcd;
bw.write(gcd + " " + lcm);
bw.flush();
bw.close();
}
// 최대공약수 구하기(유클리드 호제법)
private static int gcd(int m, int n) {
if (m % n == 0) return n; // m이 n으로 나누어 떨어지면 n이 최대공약수
// 나눈 나머지가 0이 아니면 n과 m % n으로 재귀 호출
return gcd(n, m % n);
}
}
728x90