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

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

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

 

최대공약수는 유클리드 호제법으로 구현

두 수 a, b가 있을 때 나머지가 0이 될때까지 재귀함수로 구현

나머지가 0일 때 그 수가 최대공약수

최소 공배수 : a * b / a, b의 최대공약수

 

import java.util.*;


public class Main {

	public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        int ans = gcd(a, b);
        int lcm = a * b / ans; 
        
        System.out.println(ans);
        System.out.println(lcm);
    }

    // 최대공약수를 구하기 위한 유클리드 호제법
    private static int gcd(int a, int b) {
        if(a % b == 0) {
          return b;
        } else {
          return gcd(b, a % b);
        }
    }
}