[기초 알고리즘] 수학: 최대공약수

약수

• 어떤 수를 나누어 떨어지게 하는 수 입니다.
• 약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다.

 

최대공약수 (GCD)

• 두 개 이상의 정수의 공통된 약수 중에서 가장 큰 수를 뜻합니다.

 

구현

유클리드 알고리즘 (구현)

• 두 수의 최대공약수는 작은수와 두 수를 나눈 나머지의 최대공약수와 같음

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

 

• 재귀적 구현이 가능합니다.
• 가장 효율적입니다.

 

고급

베주 항등식

• ax + by = gcd(a, b)
• 위 식을 만족하는 x, y쌍이 항상 존재 (1개 이상)