1. Problem 📃

[ 최대공약수와 최소공배수 ]

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

[ 문제 ]

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

2. Input 📇

[ 입력 ]

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

3. Output 📠

[ 출력 ]

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

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

1. 최대공약수와 최소공배수를 구할 두 값을 변수 n과 m에 각각 담아준다.
   이때, n과 m의 대소관계를 비교하여 큰 값과 작은 값을 구별하여준다.
   
   
2. 최대공약수를 만들 메서드(gcd)와 최소공배수를 만들 메서드(lcm)을 선언하여 구현해준다.
   
   
3. 우선 lcm, 매개변수로 n과 m을 받아 n이 m으로 나눈 나머지가 0이라면 n을 반환하고 그렇지 않다면 n*m값을 반환한다.
   
   
4. gcd를 구현하기 위해서는 유클리드 호제법이 필요한데, 이는 두 자연수 a, b(a>b)에 대해 b!=0 이라면 a%b를 한 후 나온 나머지 r을 이용해 b%r을 반복하면서 나누는 수가 0이 될 때 파라미터 a(매겨변수 앞)값이 두 수의 최소 공배수가 된다.
   
   
5. 출력문에 메서드를 호출해서 두 값을 호출하여 반환된 값을 출력한다.

6. Code 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static int gcd(int n, int m) {
		if (m == 0) {
			return n;
		} else {
			return gcd(m, n % m);
		}
	}

	public static int lcm(int n, int m) {
		if (n % m == 0) {
			return n;
		} else {
			return n * m;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int max = n >= m ? n : m;
		int min = n <= m ? n : m;
		
		System.out.println(gcd(max, min) + "\n" + min*max/gcd(max, min));
	}

}

7. Growth 🍄

< 최대공약수 구하는 공식 >

2개의 자연수 파라미터 a와 b (a > b)에 대해서 b!=0 이라면 a % b를 한 후 나온 나머지 값 r을 이용하여 b % r 을 계속 반복하여 나누는 수가 0이 될 때 파라미터. a값이 두 수의 최소 공배수가 된다.

public int gcd(int a, int b) {	
	if(b==0) {
        	return a;
        }
        else {
     	  	return gcd(b, a % b);
        }
}

혹은

public int gcd(int a, int b) {
	while(b != 0){
		a = b;
		b = a % b;
    	}
        return a;
}

위와 같이 구할 수 있다.

< 최소공배수를 구하는 공식 >

두 수 a, b를 곱하여 두 수 a, b에 최대공약수를 나누어준다

public int lcm(int a, int b) {
	//위에서 구한 최대공약수를 gcdNum으로 칠게용..❤️
    int lcmNum = a * b / gcdNum;
    
    return lcmNum;
}