백준 2609,1934 - 최대공약수와 최소공배수,최소공배수

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수 출력하는 것

2609 최대공약수 최소공배수 

public class Main{
    
    public static void main(String[] args) throws Exception{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input =br.readLine().split(" ");
        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt((input[1]));
        
        int gcd = getGcd(a,b);
        int lcm = (a*b)/getGcd2(a,b);
        bw.write(gcd+"\n"+lcm+"\n");
        bw.flush();
        bw.close();
        
    }
     public static int getGcd(int a,int b){
        if(b==0){
            return a;
        }else {
            return getGcd(b, a % b);
        }
    }
     public static int getGcd2(int a, int b){
       while( b != 0){
           int r= a % b;
           a = b;
           b = r;
       }
        return a;
    }
}

1934 최소공배수

public class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        String input;
        int a;
        int b;

        while(t-->0) {
            input = br.readLine();
            a = Integer.parseInt(input.substring(0,input.indexOf(" ")));
            b = Integer.parseInt(input.substring(input.indexOf(" ")+1));

            int lcm = (a * b) / getGcd(a, b);
            bw.write( lcm + "\n");
        }
        bw.flush();
        bw.close();

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

최대공약수- GCD

두 수의 최대공약수 구하는 가장 쉬운 방법은 

2부터 a와 b중 작은 수까지의 수로 나누어보는 것이다.

 

for(int i=2; i<Math.min(a,b);i++){
if(a%i==0 && b %i ==0}(maxgcd =i;}
}

시간 복잡도 O(N)으로 구리다. 

 

-유클리드 호제법 (O(logN))

 

a와 b를 나눈 나머지를 m이라고 하면, 

a와 b의 최대 공약수는 b와 m의 최대공약수와 같다.

gcd(a,b) = gcd(b, a%b) ----> m이 0일때가 최대공약수이다.

 

-세 수의 최대공약수는 gcd(a,b,c) = gcd(gcd(a,b),c) -->ab의 최대공약수와 c 사이의 최대공약수 

N개의 최대공약수로 확장가능 gcd(gcd(gcd(a,b),c),d)

 

최소공배수 (LCM)

 

a*b = 최대공약수 *최소공배수이므로 a*b/최대공약수는 최소공배수이다.

 

//재귀호출
public int getGCD(int a, int b)
{	if(b == 0) return a;
	else return getGCD(b,a%b);
}

//반복문
pulbic int getGCD(int a, int b){
	while(b != 0){
    int r = a%b;
    a=b;
    b=r;
    }
}