[Java 자바] 백준 알고리즘 2609번 답 : 최대공약수와 최소공배수 | 유클리드 알고리즘 | 유클리드 호제법

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

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

 

 

유클리드 호제법.. 까먹어서 다시 구글링해서 찾았다.

근데 그냥 공식으로 외우기엔 짜증이 났다. 찝찝하다고 해야하나..

그래서 구글링을 해봤는데 위키백과는 뭔가 너무 어려운 것 같아서.. 유튜브로 갔더니!

빛 강의를 발견했다ㅠㅡㅠ 설명 완전 이해 쏙쏙되게 해주심!! 아래 링크 걸게요!

저같은 분은 꼭 보세여 ㅎㅎ

 

https://youtu.be/J5Yl2kHPAY4

유클리드 호제법

 

유클리드 호제법은 GCD에서 끝난다. 그럼 최소공배수인 LCM은?!

 

최소공배수야 말로 진짜 간단 그 자체

 

최소공배수는 두 수의 최대공약수로 나눈 두 서로소와 최대공약수를 곱한 값이다.

 

아래 내 손글씨로 알기쉽게 정리해보았다.

 

 

따라서 LCM = a*b / GCD(a,b) 이다!

 

아래 백준 최대공약수와 최소공배수 문제에 대한 내 코드를 첨부하겠다.

 

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

public class Main {
    static int gcd(int a, int b){
        int tmp;
        if(a<b){
            tmp = a;
            a = b;
            b = tmp;
        }

        while(b!=0){
            tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }

    static int lcm(int a, int b, int g){
        return a*b/g;
    }

    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 g = gcd(a,b);

        System.out.println(g);
        System.out.println(lcm(a,b,g));
    }
}