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

* 유클리드 호제법 공부하기

* BigInteger 내장함수 gcd, lcm 사용가능

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

public class Main {

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

		int[] arr = new int[10000 + 1];

		for (int i = 1; i < arr.length; i++) {
			if (i == 1) {
				arr[i] = -1;
			} else {
				arr[i] = i;
			}
		}

		// 제곱근 범위 나누기
		for (int i = 3; i < arr.length; i++) {
			for (int j = 2; j <= Math.sqrt(i); j++) {
				if (i != j && i % j == 0) {
					arr[i] = -1;
				}
			}
		}

		int num1 = scan.nextInt();
		int num2 = scan.nextInt();
		// gcd : greatest common divisor 최대공약수
		int gcd = 1;
		// lcd : least common multiple 최소공배수

		for (int i = 2; i <= Math.min(num1, num2); i++) {
			while (num1 % i == 0 && num2 % i == 0) {
				num1 /= i;
				num2 /= i;
				gcd *= i;
			}
		}

		System.out.println(gcd);
		System.out.println(gcd * num1 * num2);

	}

}