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

📝 문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

✍ 입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

💻 출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

📃 예제 입력

24 18

📃 예제 출력

6
72

🔍내 코드

package com.focusonmx.baekjoon.CodeplusBasicMath;

import java.util.Scanner;

public class B2609 {
	static int a;
	static int b;
	static int LCM;//Least Common Multiple,최소 공배수
	static int GCD;//Greatest Common Divisor,최대 공약수
	
	public static int Euclidean(int a, int b) {//유클리드 호제법
		 int r;
		while(b!=0) {
			r=a%b;
			a=b;
			b=r;
		}
		return a;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		a= sc.nextInt();
		b= sc.nextInt();
		GCD=Euclidean(a,b);
		
		LCM=(a/GCD)*(b/GCD)*GCD;//각 수를 최대공약수로 나눴을 때 각각의 몫들과 최대공약수를 곱함.
		System.out.println(GCD);
		System.out.println(LCM);
	}

}

📖 배운점

유클리드 호제법

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법

두 양의 정수 $a, b (a>b)$에 대하여
$a=bq+r\,\left(0\leq r<a\right)a=bq+r(0≤r<a)$
라 하면, $a, b$의 최대공약수는 $b, r$의 최대공약수와 같다.
즉,

$\gcd\left(a,\ b\right)=\gcd\left(b,\ r\right)gcd(a, b)=gcd(b, r). r=0$

이라면, $a, b$의 최대공약수는 $b$가 된다.

예시 (12345와 1234의 최대 공약수)

두 수의 최대 공약수는 1이다.

반복문

def Euclidean(a, b):
   while b != 0:
       r = a % b
       a = b
       b = r
   
   return a   

재귀문

def Euclidean(a, b):

r = b % a

if r == 0:
 return a

else:
 return Euclidean(r, a)

시간복잡도를 생각하여 되도록 재귀문은 쓰지 말자.