[백준(baekjoon) 2609] 최대공약수, 최소공배수(GCD/LCM) 원리/코드/유클리드 호제법

문제 백준 2609

최대공약수(GCD) 와 최소공배수(LCM) 를 구하시오.

원리

• 최대공약수 : 유클리드 호제법 사용
• 최소공배수 : 최대공약수 활용

유클리드 호제법

• GCD(A, B) = A, B의 최대공약수
• r = A % B 일 때, GCD(A, B) = GCD(B, r)이다.
• 단, r == 0이면 GCD(B, r) = B이다.
  
  • 딱 r = A % B = 0으로, 딱 나누어 떨어지므로 최대공약수는 B

예시

A = 24, B = 82

1. GCD(24, 82)
   
   • r = 24 % 82 = 24
   • r > 0 -> GCD(82, 24)호출
2. GCD(82, 24)
   
   • r = 82 % 24 = 10
   • r > 0 -> GCD(24, 10)호출
3. GCD(24, 10)
   
   • r = 24 % 10 = 4
   • r > 0 -> GCD(10, 4)호출
4. GCD(10, 4)
   
   • r = 10 % 4 = 2
   • r > 0 -> GCD(4, 2)호출
5. GCD(4, 2)
   
   • r = 4 % 2 = 0
   • r == 0 -> gcd = 2

증명

• 서로소 : 여러 개의 수들 사이에 1 이외의 공약수가 없음을 일컫는 말.
  
  

그렇다면 전제 (a-qb)와 b가 서로소인지 어떻게 알 수 있을까?

귀류법(명제를 반대로 가정한 후 모순을 이끌어내어 가정이 거짓임을 증명)을 사용해 증명해보자.

가정 : (a-qb)와 b는 서로소가 아니다.

---

구현

원리를 파악했으니 이를 활용해서 구현해보자.

최대공약수(GCD)

즉, A와 B로 나눈 나머지를 구하여
0인지 확인 한 후 0이 아니라면 0일때 까지 반복하고
0인 경우 나눈 값이 최대공약수이므로 리턴하면 된다.

최소공배수(LCM)

A,B의 최소공배수
= 최대공약수 * (A/최대공약수) * (B/최대공약수)
= A * (B/최대공약수)

코드

Swift

1.import Foundation
2.
3.let input = readLine()!.split(separator: " ").map{ Int($0)! }
4.
5.func getGcd(_ a : Int, _ b : Int) -> Int {
6.    return b == 0 ? a : getGcd(b, a % b)
7.}
8.
9.let gcd = getGcd(input[0], input[1])
10.let lcm = input[0] * input[1] / gcd
11.
12.print(gcd)
13.print(lcm)

Java

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int a = sc.nextInt();
7.        int b = sc.nextInt();
8.
9.        int gcd = gcd(a, b);
10.        System.out.println(gcd);
11.        System.out.println(a * (b / gcd));
12.    }
13.
14.    static int gcd (int a, int b) {
15.        return b == 0 ? a : gcd(b, a % b);
16.    }
17.}

결과