방명록
- [백준 / 자바] 2609번 최대공약수와 최소공배수 - 유클리드 호제법2024년 01월 23일 17시 16분 00초에 업로드 된 글입니다.작성자: 민발자728x90
https://www.acmicpc.net/problem/2609
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
24 18
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
6 72
풀이
최대 공약수는 유클리드 호제법을 이용 -> 재귀형태로 구현
최소 공배수는 최대 공약수를 구하고 두 수의 곱을 최대 공약수로 나누면 쉽게 구할 수 있음
public class Main { 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 d = gcd(a, b); System.out.println(d); // 최소 공배수 System.out.println(a*b/d); } public static int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a%b); } }
728x90'기록 > 백준' 카테고리의 다른 글
[백준 / 자바] 10989번 수 정렬하기 3 - 계수 정렬 (0) 2024.01.24 [백준 / 자바] 1934번 최소공배수 - 유클리드 호제법 (0) 2024.01.23 [백준 / 자바] 2869번 달팽이는 올라가고 싶다 (0) 2024.01.23 [백준 / 자바] 1541번 잃어버린 괄호 - 그리디 (0) 2024.01.10 [백준 / 자바] 11047번 동전 0 - 그리디 (0) 2024.01.10 다음글이 없습니다.이전글이 없습니다.댓글