[BOJ]2609번: 최대공약수와 최소공배수(java, c++)

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

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

 

JAVA 소스

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int A = sc.nextInt();
        int B = sc.nextInt();
 
        int GCD = GCD1(A, B);
        int LCM = A * B / GCD;
 
        System.out.println(GCD);
        System.out.println(LCM);
 
    }
 
    // 재귀함수O 유클리드 호제법
    public static int GCD1(int A, int B) {
 
        if (B == 0) {
            return A;
        } else {
            return GCD1(B, A % B);
        }
    }
 
    // 재귀함수X 유클리드 호제법
    public static int GCD2(int A, int B) {
 
        while (B != 0) {
            int r = A % B;
            A = B;
            B = r;
        }
        return A;
    }
 
    // 모든 정수로 나누어보기
    public static int GCD3(int A, int B) {
        int GCD = 1;
        int iMin = (A < B) ? A : B;
 
        for (int i = 2; i <= iMin; i++) {
            if (A % i == 0 && B % i == 0) {
                GCD = i;
            }
        }
        return GCD;
    }
}

 

C++소스

#include <iostream>
 
using namespace std;
 
/*
    유클리드 호제법
    a % b = r 일때, GCD(a, b) = GCD(b, r)
*/
int GCD(int A, int B)
{
    if (B != 0)
    {
        return GCD(B, A % B);
    }
    return A;
}
 
int main()
{
    // 입출력 속도 향상
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int A, B;
    cin >> A >> B;
 
    int gcd = GCD(A, B);
    int lcm = A * B / gcd;
 
    cout << gcd << '\n' << lcm;
 
    return 0;
}

 

 

 

 

최대공약수 Greatest Common Divisor, GCD 구하기

 

TIP1

방법 1. 유클리드 호제법 이용하기

    // 재귀함수O 유클리드 호제법
    public static int GCD1(int A, int B) {
 
        if (B == 0) {
            return A;
        } else {
            return GCD1(B, A % B);
        }
    }
 
    // 재귀함수X 유클리드 호제법
    public static int GCD2(int A, int B) {
 
        while (B != 0) {
            int r = A % B;
            A = B;
            B = r;
        }
        return A;
    }

 

방법 2보다 빠르다.

항상 인수의 크기 관계를 A < B로 유지하기 위해

다음턴으로 넘길 때, 서로 위치를 바꾸어주자. 

ex. GCD(A, B) --> GCD(B, A%B)

 

 

 

*유클리드 호제법 (Euclidean algorithm)

A를 B로 나눈 나머지를  r 이라고 했을 때

GCD(A, B) = GCD(B, r)

 

r이 0일때의 B가 최대 공약수가 된다.

 

 

---

*증명*

A = aG

B = bG              이 때, a 와 b 는 서로소(Coprime)

 

A = qB + r         이라 하면, 

r = A - qB          이고, 이 때 r 과 B의 최대 공약수가 G가 됨을 증명하면 된다.

 

r = aG - qbG

  = G(a - qb)       이므로, 

                        r과 B의 최대 공약수가 G이려면, b와 (a - qb)가 서로소여야 한다. 

 

 

         귀류법을 이용하여, b와 (a - qb)가 서로소가 아니라, 공약수 m을 가졌다고 해보자.

b = mk

a - qb = mk'       라 하면,

 

a = mk' + qmk

  = m(k' + qk)     이므로

 

a = m(k' + qk)

b = mk              인데,

 

위쪽 첫번째 전제에서 a 와 b는 최대 공약수가 1인 서로소 라고 하였으므로

m = 1일 수밖에 없다. m ≠ 1 이라면 a 와 b 는 서로소가 아니게 된다.

 

         따라서 b 와 (a - qb) 가 서로소이고, 그러므로 r 과 B의 최대공약수가 G가 된다. 

 

         ∴ GCD(A, B) = GCD(B, r)

 

 

방법 2. 2부터 min(A, B)까지 모든 정수로 나누어보기

    // 모든 정수로 나누어보기
    public static int GCD3(int A, int B) {
        int GCD = 1;
        int iMin = (A < B) ? A : B;
 
        for (int i = 2; i <= iMin; i++) {
            if (A % i == 0 && B % i == 0) {
                GCD = i;
            }
        }
        return GCD;
    }

 

최대공약수를 구하는 가장 쉬운 방법.

방법1 보다 느리다.

2부터 min(A, B)까지 모든 정수로 나누어 보는 방법.

 

 

 

 

TIP2

세 수 이상의 최대 공약수는 앞에서부터 두 수씩 연산한다.

ex. GCD(A, B, C) = GCD(GCD(A, B), C)

 

 

 

 

 

 

 

최소공배수 Least Common Multiple, LCM 구하기

 

TIP3

AB = GaGb = G * Gab 이므로

LCM = Gab = AB/G