[Algorithm]자바_GCD와 LCM 구하기 :: 유클리드 호제법

 

💬 문제 설명

최대 공약수와 최소 공배수를 구하기.

다음 조건을 만족시킨다.
1. 숫자를 차례로 입력받는다.
2. 숫자 집합의 가장 큰 최대 공약수를 구한다.
3. 숫자 집합의 가장 작은 최소 공배수를 구한다.

만약 입력 된 숫자가 0이면 프로그램을 종료한다.

 

🚫 제한 사항

• n은 1,000,000 이하의 자연수 입니다

 

🔨 입출력 예

입력 - 숫자 집합을 입력한다.

100, 200, 50, 800, 70, 45, 19

출력 - 최소공배수와 최대공약수를 차례로 출력한다.

957600 1

​

💻 Solution.java

유클리드 호제법을 이용해 문제를 풀이하면 간단하다.

• 먼저, 유클리드 호제법을 이용해 최대공약수를 구하고
• 두 수를 곱한 값을 촤대 공약수로 나눠 최소공배수를 구할 수 있다.

import java.io.*;

public class Main {
	// 최소 공배수
	public static int findLCM(int a, int b) {
		if(b == 0) {
			return a;
		}
		return (a * b) / findGCD(a, b);
	}

	// 최대 공약수
	private static int findGCD(int a, int b) {
		if(b == 0) {
			return a;
		}
		return findGCD(b, a % b);
	}
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader( System.in));
		
		int prevL = 0, prevG = 0;
		String inputString = "";
		
		while(true) {
			System.out.print("Input : ");
			int num = Integer.parseInt(br.readLine());
			
			// 입력 받은 값이 0이면 종료
			if(num == 0) break;

			// 기존에 입력 받은 정수들 출력
			StringBuilder sb = new StringBuilder();
			inputString += num;
			sb.append("Input Numbers : " + inputString).append('\n');
		
			// 기존의 수와 입력 받은 값에서 최소 공배수 구하기
			int lcm = findLCM(num, prevL);
			sb.append("LCM : " + lcm).append('\n');

			// 기존의 수와 입력 받은 값에서 최대 공약수 구하기
			int gcd = findGCD(num, prevG);
			sb.append("GCD : " + gcd).append('\n');

			// lcm, gcd 출력
			System.out.println(sb);
			
			// 기존 최대 공약수, 최소 공배수 저장
			prevL = lcm;
			prevG = gcd;
			
			inputString += ",";
		}
	}
}