[BOJ] [JAVA] 13241번 최소공배수

13241번: 최소공배수

입력된 두 수의 최소공배수를 구하는 문제이다.

두 수 a, b에 대해 최대공약수 * 최소공배수 = a * b가 성립함을 이용했다.

최대공약수는 유클리드 호제법을 이용하여 구할 수 있다.

(스테인 알고리즘도 있다고 한다)

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long L = a * b / GCD(a, b);
		System.out.print(L);
	}
	
	private static long GCD(long a, long b) {
		if (a >= b) {
			long r = a % b;
			if (r == 0) return b;
			else return GCD(r, b);
		} else return GCD(b, a);
	}
}

유클리드 호제법은 a와 b의 최대공약수는 a를 b로 나눈 나머지인 r과 b의 최대공약수와 같음을 이용한 방법이다.

최대공약수를 구하는 GCD를 재귀를 통해 만들었다.