[백준 온라인 저지] 13241. 최소공배수

1. 입력

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

- 50%의 입력 중 A와 B는 1000(10^3)보다 작다.

- 다른 50%의 입력은 1000보다 크고 100000000(10^8)보다 작다.

 

2. 출력

- A와 B의 최소공배수를 한 줄에 출력한다.

 

3. 코드

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine());
        long[] num = {Long.valueOf(token.nextToken()),Long.valueOf(token.nextToken())};
        System.out.print(num[0]/findGCD(num[0],num[1])*num[1]);
	}
	
	static long findGCD(long a, long b) {
		if(b==0) return a;
		return findGCD(b, a%b);
	}
}

- 유클리드 호제법: 두 수를 나누면서 두 수의 최대공약수를 구하는 방법

1) 최대공약수가 1이 아닌 두 수: 100과 35

- 100은 35로 나누어 떨어지지 않음 -> 100%35==30과 35 비교

- 35는 30으로 나누어 떨어지지 않음 -> 35%30==5와 30 비교

- 30은 5로 나누어 떨어짐 -> 100과 35의 최대공약수는 5

2) 서로소인 두 수: 3과 5

- 5는 3으로 나누어 떨어지지 않음 -> 5%3==2와 3 비교

- 3은 2로 나누어 떨어지지 않음 -> 3%2==1과 2 비교

- 2는 1로 나누어 떨어짐 -> 3과 5의 최대공약수는 1