💡 퀵 접속: cpp.kr/gcd

gcd

C++ 표준 라이브러리의 알고리즘으로, 두 정수의 최대공약수(Greatest Common Divisor)를 계산합니다. C++17에서 도입되었습니다.

기본 사용법

#include <iostream>
#include <numeric>

int main() {
    int a = 48;
    int b = 36;
    
    // 최대공약수 계산
    int result = std::gcd(a, b);
    
    // 결과 출력
    std::cout << a << "와 " << b << "의 최대공약수: " 
              << result << std::endl;
    
    return 0;
}

실행 결과:

48와 36의 최대공약수: 12

음수 처리

#include <iostream>
#include <numeric>

int main() {
    int a = -48;
    int b = 36;
    
    // 음수가 포함된 최대공약수 계산
    int result = std::gcd(a, b);
    
    // 결과 출력
    std::cout << a << "와 " << b << "의 최대공약수: " 
              << result << std::endl;
    
    return 0;
}

실행 결과:

-48와 36의 최대공약수: 12

여러 수의 최대공약수

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> numbers = {48, 36, 24, 12};
    
    // 여러 수의 최대공약수 계산
    int result = numbers[0];
    for (size_t i = 1; i < numbers.size(); ++i) {
        result = std::gcd(result, numbers[i]);
    }
    
    // 결과 출력
    std::cout << "여러 수의 최대공약수: " << result << std::endl;
    
    return 0;
}

실행 결과:

여러 수의 최대공약수: 12

참고사항

gcd는 numeric 헤더에 정의되어 있습니다.
C++17에서 도입되었습니다.
입력 값이 0인 경우, 다른 입력 값의 절대값을 반환합니다.
두 입력 값이 모두 0인 경우, 0을 반환합니다.
음수 입력의 경우, 결과는 항상 양수입니다.
시간 복잡도는 O(log(min(a, b)))입니다.

함수	설명
gcd(m, n)	두 정수 m과 n의 최대공약수 계산