[백준] java 13241 최소공배수(유클리드 호제법)

https://www.acmicpc.net/problem/13241

문제

정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.

예:

10은 5의 배수이다 (5*2 = 10)
10은 10의 배수이다(10*1 = 10)
6은 1의 배수이다(1*6 = 6)
20은 1, 2, 4,5,10,20의 배수이다.
다른 예:

2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
10과 20의 최소공배수는 20이다.
5와 3의 최소공배수는 15이다.
당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.

입력

한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.

50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다.

추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.

풀이과정

바로 이전 문제와 거의 똑같은 문제이다.

이전 문제에서 제출했던 풀이이다.

import java.io.*;
import java.util.StringTokenizer;

public class Main{

	public static void main(String[] args) throws Exception {
		solved();
	}
	public static void solved() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		String A = st.nextToken();
		String B = st.nextToken();
		if (Long.parseLong(A) > 1000) {
			long a = Long.parseLong(A), b = Long.parseLong(B);

			int sum = 1;

			for (int j = 2; j <= (Math.min(a, b)); j++) {

				if (a % j == 0 && b % j == 0) {
					a /= j;
					b /= j;
					sum *= j;
					j = 1;
				}

			}
			System.out.println(sum * a * b);
		} else {
			int a = Integer.parseInt(A), b = Integer.parseInt(B);

			int sum = 1;
			for (int j = 2; j <= (Math.min(a, b)); j++) {

				if (a % j == 0 && b % j == 0) {
					a /= j;
					b /= j;
					sum *= j;
					j = 1;
				}

			}
			System.out.println(sum * a * b);
		}
	}
}

유클리드 호제법 사용한 풀이

최대 공약수와 최소 공배수를 구할 때 간단한 방법이 하나 있는데, 바로 유클리드 호제법이라고 한다.

유클리드 호제법을 사용하면 코드가 엄청나게 짧아진다.

일단 유클리드 호제법의 정의를 알아보자.

유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이며, 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
즉, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라고 한다.
[ 출처: 위키백과 ]

다음은 유클리드 호제법을 사용한 풀이이다. 코드가 더 효율적이고 매우 간결해진 것을 볼 수 있다.

import java.io.*;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		long longA = Long.parseLong(st.nextToken());long longB = Long.parseLong(st.nextToken())
		long a = longA, b = longB, temp;

		while( b != 0 ){

			temp = a % b;
			a = b;
			b = temp;

		}
		System.out.println(longA * longB / a);
	}
}