백준/2609 최대공약수와 최대공배수 // 유클리드 호제법

최대공약수와 최소공배수 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

80267

46401

37707

58.422%

문제

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

입력

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

 

출력

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

예제 입력 1 복사

24 18

예제 출력 1 복사

6
72

---

풀이

틀린 코드

각 수를 소인수분해해서 최대 공약수 최소공배수를 구하려고했지만 실패

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        int num1 = Integer.parseInt(input[0]);
        int num2 = Integer.parseInt(input[1]);
        int num1Temp = num1;
        int num2Temp = num2;

        Map<Integer, Integer> num1Map = new HashMap<>();
        Map<Integer, Integer> num2Map = new HashMap<>();

        int a = 2;
        while (num1 > 1) {
            if (num1 % a == 0) {
                num1 = num1 / a;
                num1Map.put(a, num1Map.getOrDefault(a, 0) + 1);
                a = 2;
            }
            else{
                a++;
            }
        }
        a= 2;
        while (num2 > 1) {
            if (num2 % a == 0) {
                num2 = num2 / a;
                num2Map.put(a, num2Map.getOrDefault(a, 0) + 1);
                a = 2;
            }
            else{
                a++;
            }
        }

        int lcm = 1;  //최소공배수
        int gcd = 1; // 최대공약수

//        bw.write(num1Map.toString()+"\n");
//        bw.write(num2Map.toString()+"\n");

        if (num1Map.size() >= num2Map.size()) {
            for (Entry<Integer, Integer> entry : num1Map.entrySet()) {
                int key = entry.getKey();
                int value = entry.getValue();
                if (num2Map.containsKey(key)) {
                    int num2Value = num2Map.get(key);
                    if (value > num2Value) {
                        gcd *= Math.pow(key, num2Value);
                        lcm *= Math.pow(key, value);
                    }
                    else{
                        lcm *= Math.pow(key, num2Value);
                        gcd *= Math.pow(key, value);
                    }
                }
                else{
                    lcm *= key;
                }
            }
        }
        else{
            for (Entry<Integer, Integer> entry : num2Map.entrySet()) {
                int key = entry.getKey();
                int value = entry.getValue();
                if (num1Map.containsKey(key)) {
                    int num1Value = num1Map.get(key);
                    if (value > num1Value) {
                        gcd *= Math.pow(key, num1Value);
                        lcm *= Math.pow(key, value);
                    }
                    else{
                        lcm *= Math.pow(key, num1Value);
                        gcd *= Math.pow(key, value);
                    }
                }
                else{
                    lcm *= key;
                }
            }
        }


        if (lcm == 1 && gcd == 1) { //서로 같은 약수가 없을때
            lcm = num1Temp * num2Temp;
        }

        bw.write(gcd + "\n" + lcm);

        bw.flush();
        bw.close();

    }

}

 

 

다른사람코드

유클리드 호제법을 이용한다.

 

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

 

즉

GCD(a, b) = GCD(b, r) 와 같고 여기서 r은 나머지를 의미한다.

 

간단하게

두 수 a,b 의 최대공약수는

GCD(a,b) = GCD(b,r) 이고 r은 a/b의 나머지를 의미한다 a를 b로 나눈 나머지)

 

그래서 결국

GCD(a,b) = GCD(b,r)  = GCD(r,b/r) .... 반복해서 GCD(어떤값,0)  이 될때까지 반복한다. 나머지가 0이된순간 그 어떤값이 최대 공약수이다.

 

예)

GCD(581, 322)일 때 r(나머지) = 259이다. 즉, GCD(581, 322) = GCD(322, 259)이다.그럼 다시 GCD(322, 259)를 보면 r=63이다. 그러면 GCD(322, 259) = GCD(259, 63)이다.또 다시 GCD(259, 63)을 보면 r=7이다. 즉, GCD(259, 63) = GCD(63, 7)이다.

다시 GCD(63, 7)을 보면 r=0 이다. 그러면 GCD(63, 7) = GCD(7, 0)이다.

 

 

두 수 a,b의 최소공배수는

(a * b) / GCD(a,b)

 

a와 b를 곱한값을 최대공약수로 나눈다. 

 

 

 

수정된 풀이

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        int a = Integer.parseInt(input[0]) ;
        int b = Integer.parseInt(input[1]);

        bw.write(gcd(a, b) + "\n" + lcm(a, b));

        bw.flush();
        bw.close();

    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b); //재귀적으로 실행되면서 마지막에 최대공약수를 가지고 리턴될것이니까 return을 붙여준다.
    }

    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }


}

 

 

 

[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]