[BAEKJOON] 2609번 최대공약수와 최소공배수

---

최대공약수 구하기

※ 이 부분의 본문은 유클리드 호제법입니다.

똑같이 두 수 192와 72의 최대공약수를 이번에는 호제법으로 구하여 보자. 일단 192을 72로 나누어 나머지를 구한다.

192 = 72 * 2 + 48

이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다. 이번에는 72을 나머지인 48로 나눈다.

72 = 48 * 1 + 24

이와 같은 연산을 나머지가 0이 될 때까지 반복한다.

48 = 24 * 2 + 0

나머지가 0이 되었으므로 연산을 중지한다. 이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다.

// 유클리드 호제법 (a를 b로 나눈 나머지가 0보다 클 때 까지 반복)
static int gcd(int a, int b){ // 최대공약수
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

// 유클리드 호제법 재귀함수
static int GCD(int a, int b){ // 최대공약수
	if (a%b == 0) {
		return b;
	}
	return GCD(b, a % b);
}

최소공배수 구하기

24 * 36 = 12 * 2 * 12 *3

           = 12 * 2 * 3 * 12

           = 72 * 12

두 수 24와 36 그리고 최대공약수 12와 최소공배수의 72를 살펴보자.

두 수의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다.

static int lcm(int a, int b){ // 최소 공배수
	// 0이 아닌 두 수의 곱 / 두 수의 최대공약수
    return a * b / gcd(a,b);
}

// 유클리드 사용
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		
		System.out.println(gcd(a, b));
		System.out.println(lcm(a, b));
	}
	
	static int gcd(int a, int b){ // 최대공약수
		while(b!=0){
			int r = a%b;
			a= b;
			b= r;
		}
		return a;
	}
	
	static int lcm(int a, int b){ // 최소 공배수
		// 0이 아닌 두 수의 곱 / 두 수의 최대공약수
	    return a * b / gcd(a,b);
	}
	
	static int GCD(int a, int b){ // 최대 공약수
		if (a%b == 0) {
			return b;
		}
		return GCD(b, a % b);
	}

}

---

// 유클리드 X, 반복문 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a=Integer.parseInt(st.nextToken());
		int b=Integer.parseInt(st.nextToken());
		int max, min, greatest=0, least=0;
		
		if(a>b) {
			max = a;
			min = b;
		}
		else{
			max = b;
			min = a;
		}
		for(int i=1; i<=min; i++) {
			if(max%i==0 && min%i==0) {
				greatest = i;
			}
			if((max*i)%min==0 && least==0) {
				least = max*i;
			}
		}
		System.out.println(greatest+"\n"+least);
	}
}

[출처]

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

2609번: 최대공약수와 최소공배수