[알고리즘][수학] 최대공약수, 최소공배수 구하기 - 유클리드 호제법

 

◇  설명

   □  정의, 특징

      ●  유클리드 호제법 ( Euclidean algorithm )

        -  2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나
        -  호제법  :  두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘
        -  2개의 자연수 a, b (단, a > b)에 대해서 a를 b로 나눈 나머지를 r이라 하면,
           a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
           b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여
           나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

◇  코드

import java.util.Scanner;

public class Main_2609 {

	public static int gcd(int a, int b) {
		return a % b == 0 ? b : gcd(b, a % b);
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n1 = sc.nextInt(), n2 = sc.nextInt();
		sc.close();

		int a = n1 > n2 ? n1 : n2, b = n2 > n1 ? n1 : n2;
		int gcd, lcm, r; // gcd : greatest common factor, lcm : Least Common Multiple, r : remainder

		// way 1
		gcd = gcd(a, b);

		// way 2
		while (true) {
			r = a % b;
			if (r == 0)
				break;
			a = b;
			b = r;
		}
		gcd = b;
        
		lcm = a * b / gcd;

		System.out.println(gcd + "\n" + lcm);
	}
}