2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
예제 입력 1
24 18
예제 출력 1
6
72
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int gcd(int a, int b) { // 최대공약수
if(b == 0)
return a;
else
return gcd(b, a % b);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int gcd = gcd(a, b);
int lcm = (a * b) / gcd;
System.out.println(gcd);
System.out.println(lcm);
}
}
유클리드 호제법을 통해 GCD(=최대공약수)를 구한다.
GCD를 통해 LCM(최소공배수)를 구한다.
왜 가능한지 굳이 이해하려고 하지 말자. 어차피 까먹는다.
GCD, LCM은 그냥 외우자.
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
[BOJ] 1850 - 최대공약수 JAVA (0) | 2021.01.15 |
---|---|
[BOJ] 1934 - 최소공배수 JAVA (0) | 2021.01.15 |
[BOJ] 1158 - 요세푸스 문제 JAVA (0) | 2021.01.15 |
[BOJ] 1406 - 에디터 JAVA (0) | 2021.01.15 |
[BOJ] 11656 - 접미사 배열 JAVA (0) | 2021.01.15 |