백준 2609 - 최대공약수와 최소공배수

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

 

1. 유형

수학

 

2. 풀이

유클리드 호제법으로 최대공약수 구한다.

최대공약수를 구했으면, 최소 공배수도 구하는게 가능

 

3. 코드

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a=stoi(st.nextToken());
		int b=stoi(st.nextToken());
		int answer;
		if(a>b) { answer = dfs(a, b);}
		else answer = dfs(b, a);
		int answer2 = (b/answer)*(a/answer)*answer;
		System.out.println(answer);
		System.out.println(answer2);
	}
	static int dfs(int a, int b){
		if(b==0) {
			return a;
		}
		return dfs(b, a%b);
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}
//유클리드 호제법