[백준] 2609번 : 최대공약수와 최소공배수(JAVA)

오래망갑에 문제푼 은구씨.gif

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

2609번: 최대공약수와 최소공배수

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 16단계

 

수학3의 카테고리에 포함되어 있는 문제이다.

 

최대공약수(Greatest Common Divisor)와

 

최소공배수(Least Common Multiple)를 구하는 문제이다.

 

GCD를 구하는 가장 쉬운 방법은 "유클리드 호제법"을 이용하는 것이다.

 

LCM을 구하는 방법은 두 수의 곱과 두 수의 최대공약수를 이용하여 구할 수 있다.

 

여담으로 유클리드 호제법은 인류 최초의 알고리즘이라고 한다.

import java.util.Scanner;

public class Question_2609 {

	public static int gcd(int A, int B) {
		int temp = 0;
		
		while(B > 0) {
			temp = B;
			B = A % B;
			A = temp;
		}
		return A;
	}
	
	public static int lcm(int A, int B) {
		return (A * B) / gcd(A, B);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int A, B;
		
		A = sc.nextInt();
		B = sc.nextInt();
		
		System.out.println(gcd(A, B));
		System.out.println(lcm(A, B));
	}
}