최대공약수(GCD)_Euclidean, 최소공배수(LCM)

최대공약수(Greatest Common Divisor) 

최대공약수란, 두 수의 공통된 약수들 중 가장 작은 수이다.

예를 들어, 20과 12의 약수는 다음과 같고 공통된 약수 중 가장 큰 수는 4이다.

 

20 : 1, 2, 4, 5, 10, 20

12 : 1, 2, 3, 4, 6, 12

 

두 수의 최대 공약수를 구하는 가장 원초적인 방법은 두 수의 약수를 모두 구하고, 이중 for문으로 공통인 약수를 탐색하면서 최댓값을 찾는 것이다. 

 

#include <vector>
#include <iostream>
using namespace std;

vector<int> getDivisor(int n) {

    vector<int> v;
    for (int i=1; i*i<=n; i++) {
        if (n%i == 0) v.push_back(i);
    }
    for (int i=(int)v.size()-1; i>=0; i--) {
        if (v[i] == n/v[i]) continue;
        v.push_back(n/v[i]);
    }
    return v;
}

void printvec(vector<int> v) {

    for (int i=0; i<v.size(); i++)
        cout<<v[i]<<" ";
    cout<<endl;
}

int main() {

    int n1 = 20, n2 = 12;
    vector<int> v1 = getDivisor(n1); //n1의 약수 목록
    vector<int> v2 = getDivisor(n2); //n2의 약수 목록

    printvec(v1);
    printvec(v2);

    int mx = 1;
    for (int i=0; i<v1.size(); i++) { //n1과 n2의 공약수 중 최댓값 찾기
        for (int j=0; j<v2.size(); j++) {
            if (v1[i] == v2[j]) mx = max(mx, v1[i]);
        }
    }
    printf("GCD: %d\n", mx);
    return 0;
}

/*
output:
1 2 4 5 10 20 
1 2 3 4 6 12 
GCD: 4
*/

 

 

 

유클리드 호제법(Euclidean Algorithm)으로 GCD 구하기

위의 방법으로도 최대공약수를 구할 수 있지만, 유클리드 호제법을 이용하면 이보다 더 간단하게 구현할 수 있다.

유클리드 호제법이란, 다음과 같은 두 성질을 말한다.

 

1) a > b 일 때 gcd(a, b)는 gcd(b, a%b)와 같다.

2) gcd(n, 0) = n 이다. (0은 모든 수의 배수이므로, 모든 수를 약수로 가진다. 따라서 n과 0의 최대공약수는 n이다.)

 

이는 재귀함수로 구현하거나 while문을 이용하여 구현할 수 있다.

 

#include <iostream>
using namespace std;

int gcd_recur(int a, int b) { //재귀를 이용한 유클리드 호제법
    if (b == 0) return a;
    return gcd_recur(b, a%b);
}

int gcd_while(int a, int b) { //while문을 이용한 유클리드 호제법

    while (b != 0) {
        int tmp = b;
        b = a%b;
        a = tmp;
    }
    return a;
}

int main() {

    cout<<"재귀를 이용한 gcd"<<endl;
    cout<<gcd_recur(10, 5)<<endl;
    cout<<gcd_recur(20, 10)<<endl;
    cout<<gcd_recur(36, 18)<<endl;
    cout<<gcd_recur(36, 40)<<endl<<endl;

    cout<<"while문을 이용한 gcd"<<endl;
    cout<<gcd_while(10, 5)<<endl;
    cout<<gcd_while(20, 10)<<endl;
    cout<<gcd_while(36, 18)<<endl;
    cout<<gcd_while(36, 40)<<endl<<endl; 
}

/*
output:
재귀를 이용한 gcd
5
10
18
4

while문을 이용한 gcd
5
10
18
4
*/

 

 

 

최소공배수(Least Common Multiple)

최대공배수란, 두수의 공통된 배수 중 가장 작은 수이다.

예를 들어, 10과 5의 공배수는 다음과 같고, 최대 공배수는 10이다.

 

10 - 10, 20, 30, 40 ...

5 - 5, 10, 15, 20, 25, ... 

 

최소공배수는 다음과 같은 성질을 이용하여 구한다.

a * b = gcd(a, b)*lcm(a, b)

lcm(a, b) = a*b/gcd(a, b)

 

#include <iostream>
using namespace std;

//LCM(Least Common Multiple) - 최소공배수
//a*b = gcd(a, b)*lcm(a, b)
//lcm(a, b) = a*b/gcd(a, b)
//int overflow를 방지하기 위해서 a/gcd(a, b)*b로 계산

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

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

int main() {

    cout<<"lcm"<<endl;
    cout<<lcm(10, 5)<<endl;
    cout<<lcm(20, 10)<<endl;
    cout<<lcm(36, 18)<<endl;
    cout<<lcm(36, 40)<<endl;  
}

/*
output:
lcm
10
20
36
360
*/