[이산수학] 최대공약수와 최소공배수 (C++)

최대공약수

Greatest Common Divisor라는 명칭에서 알 수 있듯이, 이는 공약수 중 최댓값을 의미한다.

 

식

GCD(a, b) = GCD(b, a mod b)

 

코드

이를 코드로 나타내보면 이렇게 된다;

int gcd(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

사용처

프로그래머스의 이 문제 --> https://school.programmers.co.kr/learn/courses/30/lessons/120808에서 기약분수를 구하기 위해 사용할 수 있다.

 

1. 분자와 분모를 통일해준다. 이때, 서로의 분모를 서로의 분자에게 곱해주는 식으로 통일해준다.

2. 이후 분자와 분모의 최대공약수로 분자와 분모를 나눠준다.

---

최소공배수

Least Common Multiple이라는 명칭에서 알 수 있듯이, 이는 공배수 중 최솟값을 의미한다. 

 

식

일반적으로, 최대공약수를 이용하여 구한다;

 

LCM(a, b) = a * b / GCD(a, b)

 

코드​

이 과정을 코드로 간단하게 나타내보면 이렇게 된다;

int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}

 

사용처

나중에 코딩테스트 문제를 풀어보다가 사용처를 발견하면 적겠다!