본문 바로가기

Programming/BOJ

BOJ 2609 · 최대공약수와 최소공배수


알고리즘 분류 : 수학  


최대공약수(GCD; greatest common divisor)는 유클리드 호제법(Euclidean algorithm)을 이용하여 구현할 수 있다.

  • r은 x를 y로 나눈 나머지 (r = x%y) 
  • GCD(x, y) = GCD(y, r) 를 r이 0이 될 때까지 반복적으로 수행
  • r이 0일 때, y는 최대공약수이다.

최소공배수(LCM; least common multiple)는 미리 구한 최대공약수를 이용하여 구현할 수 있다.

  • g = GCD(x, y)
  • LCM = (x*y)/g



C++ 소스코드


#include <iostream>
using namespace std;

int gcd(int x, int y) {
    while (y != 0) {
        int r = x%y;
        x = y;
        y = r;
    }
    return x;
}

int lcm(int x, int y) {
    return (x*y)/gcd(x,y);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a,b) << '\n';
    cout << lcm(a,b) << '\n';
    return 0;
}


✓ gcd 함수는 재귀함수로 구현할 수 있다.


int gcd(int x, int y) {
    if (y == 0) return x;
    else return gcd(y, x%y);
}




Python 3 소스코드


def gcd(x, y):
    while y is not 0:
        r = x%y
        x = y
        y = r
    return x

def lcm(x, y):
    return (x*y)//gcd(x,y)

a, b = map(int, input().split())
print(gcd(a,b))
print(lcm(a,b))




참고


태그