[백준 | Java Bronze VI] (#2609) 최대공약수와 최소공배수

문제

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

 

---

첫번째 코드 - 성공

첫번째로 가장 직관적인 최대공약수/최소공배수를 구하도록 풀었던 코드이다. 다른 효율적인 방법이 있었던 것 같지만 풀 때 기억이 나지 않았다 

package week8.baek;

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

public class B2609 {
    //최대 공약수
    public static int max(int a, int b){
        System.out.println(a + " " + b);

        for(int i=b; i>0; i--){
            if(a % i == 0 && b % i == 0) return i;
        }
        return -1;
    }

    //최소 공배수
    public static int min(int a, int b){
        for(int i=b; i <= a*b; i++){
            if(i % a == 0 && i % b == 0) return i;
        }

        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        int n = Integer.parseInt(input.split(" ")[0]);
        int m = Integer.parseInt(input.split(" ")[1]);

        int[] a = new int[] {n, m};
        Arrays.sort(a);

        System.out.println(max(a[0],a[1]) + "\n" + min(a[0],a[1]));
    }
}

 

개선 1 - (A와 B의 최소 공배수) = (A * B) / (A와 B의 최대 공약수)

package week8.baek;

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

public class B2609 {
    //최대 공약수
    public static int max(int a, int b){
        System.out.println(a + " " + b);

        for(int i=b; i>0; i--){
            if(a % i == 0 && b % i == 0) return i;
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        int n = Integer.parseInt(input.split(" ")[0]);
        int m = Integer.parseInt(input.split(" ")[1]);

        int[] a = new int[] {n, m};
        Arrays.sort(a);

        int max = max(a[0], a[1]);
        System.out.println(max(a[0],a[1]) + "\n" + n * m / max);
    }
}

 

개선 2 - 유클리드 호제법

static int gdc(int a, int b) { 
        if(a<b) // 유클리드 호제법 조건
        {
            int temp = a;
            a = b;
            b = temp;
        }
        while(b!=0) { // 유클리드 호제법
            int r=a%b;
            a=b;
            b=r;
        }
        return a;
    }

 

---

출처

 

https://cobook.tistory.com/49

[Java]최대 공약수, 최소 공배수 구하기(feat.유클리드 호제법)