[BOJ] 2609. 최대공약수와 최소공배수

BaekJoon 2609. 최대공약수와 최소공배수

* 문제의 저작권은 BOJ 및 문제를 만든 사람에게 있습니다.

 

 

 

 

 

[문제 접근]

최대공약수는 a,b 중에 작은 수까지만 for문을 돌려서 a,b와 나누었을 때 0이면 최대공약수

그리고 a/gcd와 b/gcd를 곱하고 gcd를 다시 곱해준다

 

근데 이렇게 구하는 것 보다 유클리드 호제법을 사용하면 더 빨리 구할 수 있다고 한다.

 

 

 

 

 

 

 

 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2609 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		
		int gcd = 1; //최대공약수
		int cm = 1; //최소 공배수
		
		for (int i = 2; i <= Math.min(a,b); i++) {
			if (a % i == 0 && b % i == 0) {
				gcd = i;
			}
		}
		
		cm = (a / gcd ) * (b / gcd);
		
		
		System.out.println(gcd);
		System.out.println(cm*gcd);

	}
}