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

최대공약수를 구하기 위한 유클리드 호제법을 처음 알게 되었다.

알고리즘이 간단하여 금방 외울 수 있었다.

 

어떤 수 a와 b의 최대공약수는 b, a%b의 최대공약수와 같다는 성질을 이용한 알고리즘 이다.

재귀호출로 구현하는 방법과 반복문으로 구현하는 방법이 있다.

static int gcd1(int a, int b) { //재귀 사용
        if(b==0)
            return a;
        return gcd1(b, a%b);
    }
    
    static int gcd2(int a, int b) { //반복문 사용
        while(b!=0) {
            int r = a%b;
            a=b;
            b=r;
        }
        return a;
    }

 

또한 최소공배수를 구할 때도 최대공약수를 이용해 구할 수 있다.

최소공배수 lcm은 a * b / 최대공약수 를 통해 구할 수 있다.

최소공배수는 최대 a * b까지도 나올 수 있으므로 지정한 자료형의 범위를 초과 할 수 있다.

문제의 범위를 잘 체크해서 올바른 자료형을 써줘야 한다.

 

import java.util.Scanner;
 
//최대공약수와 최소공배수
public class Q2609 {
    static int gcd(int a, int b) {
        if(b==0)
            return a;
        return gcd(b, a%b);
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int gcd = gcd(a, b);
        int lcm = (a*b/gcd); //최소 공배수 구하기
        System.out.println(gcd);
        System.out.println(lcm);
        
    }
 
}