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

문제

코드

import java.util.Scanner;



public class Main {

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

		Scanner scanner = new Scanner(System.in);

		int[] numbers = new int[2];



		for (int i = 0; i < numbers.length; i++) {

			numbers[i] = scanner.nextInt();

		}



		operation(numbers[0], numbers[1]);

	}



	public static void operation(int a, int b) {

		// 최대공약수(GCD) : 두 수 A B의 최대공약수는 A와 B의 공통된 약 중에서 가장 큰 정수이다.

		// 최소공배수(LCM) : 두 수 A B의 최소공배수는 A와 B의 공통된 배수 중에서 가장 작은 정수이다.



		int GCD = 0;

		int A = a;

		int B = b;



		// 재귀함수를 사용하지 않은 유클리드 호제법(최대공약수)

		while (B != 0) {

			int R = A % B;

			A = B;

			B = R;

			GCD = A; 

		}

		System.out.println(GCD);

		

		// 최소공배수 : 최대공약수 * (A / 최대공약수) * (B / 최대공약수)

		int LCM = GCD * (a / GCD) * (b / GCD);

		System.out.println(LCM);

	}

}

출처

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