[JAVA] 백준 13241번- 최소공배수

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

13241번: 최소공배수

 

import java.util.*;

public class Main {
    public static long gcd(long a, long b){
        while(b!=0){
            long r=a%b;
            a=b;
            b=r;
        }
        return a;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        long b = sc.nextInt();

        long answer = a * b / gcd(a, b);

        System.out.println(answer);
    }
}

 

최대공배수는 최대공약수를 통해 구할 수 있다.

그러므로 최대공약수를 구하는 함수를 따로 뺐다.

유클리드 호제법을 사용하면 최대공약수를 쉽게 구할 수 있다.

a를 b로 나눈 나머지가 r일 때, r이 0이 되는 순간의 나누는 수가 최대공약수이다. 

 

예를 들면, 

gcd(12345, 123) 

12345를 123으로 나눈다. 나누어 떨어지지 않고 나머지가 45가 나온다.

gcd(123, 45)

그리고 123을 45로 나눈다. 이런식으로 계속 나눈다.

gcd(45, 33) = gcd(33, 12) = gcd(12, 9) = gcd(9,3) = gcd(3,0)

이 때 나머지가 0 이 되므로 3이 최대공약수이다.

 

이렇게 구한 최대공약수를 이용하여 최소공배수를 구한다.

두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수로 나눈 것과 같다.