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

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	128MB	41418	24509	20009	61.665%

 

문제

 

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

 

입력

 

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

 

출력

 

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

 

예제 입력

 

24 18

 

예제 출력

 

6 72

 

---

느낀점

 

두 수의 최대공약수 최소공배수를 생각해 for문으로 만들어 계산하였더니 런타임 에러가 계속 발생했다..

헤매던 끝에 유클리드 호제법을 알게 되었다. //까먹지 말자ㅏㅏ

 

- 유클리드 호제법이란? 

 

두 수 a, b ∈ ℤ 이고, r는 a를 b로 나눈 나머지이다. 이 때 r은 (0 ≤ r < b) 이고, a ≥ b 이다.

이 때 a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.

아래와 같은 식이 성립하게 된다.

GCD(a, b) = GCD(b, r)

 

이때 최소 공배수는 두 자연수 즉, a와 b의 곱을 최대 공약수로 나눈 값이다.

 

시간 초과 당한 코드

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        
        int num1,num2;
        
        num1 = input.nextInt();
        num2 = input.nextInt();

        
        if(num2 > num1) { //num1의 크기를 더 크게 하기
            int n = num1;
            num1 = num2;
            num2 = n;
        }

		//최대공약수 구하기 
        for(int i = num2; i > 0; i-- ){ // 작은 수 num2에서 1까지 반복
            if(num2 % i == 0 && num1 % i == 0){ // 두 수 모두 나눠져 나머지가 0이면 최대공약수
                System.out.println(i);
                break;
            }
        }

		//최소공배수 구하기 
        for(int j = num1; j < 100000; j++){ // 큰 수 num1에서 큰수까지 반복
            if(j % num1 == 0 && j % num2 ==0){ // 두 수 모두 수에서 나눠 0이 되면 최소공배수
                System.out.println(j);
                break;
            }
        }
    }
}

 

---

 

작성 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
 
		Scanner input = new Scanner(System.in);
	
		int num1 = input.nextInt();// 변수 입력 받기
		int num2 = input.nextInt();
 
		int max = gcd(num1, num2);	
 
		System.out.println(max);
		System.out.println(num1 * num2 / max);  
        // 최소 공배수는 두 자연수의 곱을 최대 공약수로 나눈 값에 해당
 
	}
 
	public static int gcd(int num1, int num2) { // 최대공약수 재귀 방식
		if (num2 == 0)
			return num1;
		return gcd(num2, num1 % num2); // GCD(a, b) = GCD(b, r)이므로 (r = a % b)
	}
}

 

---