본문 바로가기
알고리즘/백준

[백준 2609] 최대공약수와 최소공배수

by binghe819 2020. 4. 27.

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

 

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

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net


1. 풀이

유클리드 호제법  을 사용하여 풀이하는 문제이다.

 

자세한 내용은 위 링크를 가서 확인하면 알 수 있다.

 

  • 최대공약수 = 유클리드 호제법을 이용.
  • 최소공배수 = 두 수의 곱 /  두 수의 최대공약수

2. 코드

import java.util.*;

public class Main {

    // 최대공약수
    public static int gcd(int a, int b){
        if(b == 0)
            return a;
        return gcd(b, a%b);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        System.out.println(gcd(a,b));
        System.out.println((a*b)/gcd(a,b));

        sc.close();
        return;
    }
}

댓글