7회차 - 최대공약수와 최소공배수

---

최대공약수와 최소공배수

 

 두 자연수의 최대 공약수와 최소 공배수를 계산하는 프로그램을 작성해보자.

• 최대공약수(GCD)란 두 정수 A와 B에 모두 나누어 떨어지는 가장 큰 공통의 약수를 의미한다.
• 최소공배수(LCM)란 A의 배수이면서 동시에 B의 배수가 되는 가장 작은 공통의 배수를 나타낸다.

 

입력 형식

 첫 줄에는 테스트케이스의 수 T가 1이상 100이하의 자연수로 주어진다.

이후 총 T줄에 걸쳐서 한 줄에 하나의 테스트케이스에 대한 입력이 주어진다.

• 각 테스트케이스의 입력은 한 줄에 두 자연수가 공백으로 구분되어 주어진다.
• 각 자연수는 1이상 10억이하의 자연수이다.

 

출력 형식

 각 테스트케이스마다 두 줄에 걸쳐 결과를 출력한다.

• 각 테스트케이스의 첫 줄에는 테스트케이스의 번호를 Case #%d: 형식으로 출력한다. 대소문자와 공백에 주의한다.
• 두 번째 줄에는 최대 공약수와 최소 공배수를 공백으로 구분하여 순서대로 출력한다. 

 

---

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	public static void testCase(int caseIndex)
	{   //각 테스트케이스에 대하여
		int num1 = scanner.nextInt();
		int num2 = scanner.nextInt();

		// 두 숫자의 최대 공약수와 최소 공배수를 계산한다
		long gcd =  MathUtil.getGCD(num1, num2);
		long lcm =  MathUtil.getLCM(num1, num2);

		// 정답을 출력한다
		System.out.printf("Case #%d:\n", caseIndex);
		System.out.printf("%d %d\n", gcd,lcm);
	}

	public static void main(String[] args) throws Exception {
		int caseSize = scanner.nextInt();

		for (int caseIndex = 1; caseIndex <= caseSize; caseIndex += 1) {
			testCase(caseIndex);
		}
	}

}

class MathUtil{

	/**
	 * a와 b의 최대 공약수를 계산하는 함수
	 *
	 * @param a
	 * @param b
	 * @return
	 */
	static long getGCD(long a, long b)
	{
		while( a % b != 0 ){
			long c = a % b;
			a = b;
			b = c;
		}
		return b;
	}

	/**
	 * a와 b의 최소 공배수를 계산하는 함수
	 *
	 * @param a
	 * @param b
	 * @return
	 */
	static long getLCM(long a, long b)
	{
		return a * b / getGCD(a,b);
	}
	 
}

---