MENU

[BOJ][Java] 2609번 - 최대공약수와 최대공배수

글이 정상적으로 보이지 않는다면 아래 주소로 접속해 주세요. https://egg-programmer.tistory.com/156

문제

백준 2609번 문제: 최대공약수와 최대공배수

문제 설명

최대공약수와 최소공배수를 구하는 문제

최대공약수를 구하고 그것을 바탕으로 최소공배수를 구하면 된다.
최대공약수와 최소공배수는 아래와 같이 큰 값에서 작은 값의 나머지 값을 구해 0이 될 때까지 반복해서 구할 수 있다.

data-origin-width="0" data-origin-height="0"

 invalid-file

성공 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int first = sc.nextInt();
        int second = sc.nextInt();
        sc.close();

        int big = Math.max(first, second);
        int small = Math.min(first, second);

        System.out.println(gcd(big, small));
        System.out.println((first * second) / gcd(big, small));        
    }

    public static long gcd(int first, int second) {
        if (second <= 0) return first;

        int temp = first;
        first = second;
        second = temp % second;

        return gcd(first, second);
    }

}