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

1. 약수

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

 

 

2. 소인수

• 주어진 자연수를 나누어 떨어뜨리는 약수중에서 소수인 약수​

 

소인수분해

• 합성수를 소인수들만의 곱으로 나타내는 것

\[
n = p_1^{a_1} \,\cdot\, p_2^{a_2} \,\cdot\, \cdots \,\cdot\, p_k^{a_k}
\]

 

약수의 합

• n의 모든 양의 약수를 더한 값
• ✅ 소인수분해 형태로 표현

\[
1 + p + p^2 + \cdots + p^a 
= \frac{p^{a+1} - 1}{p - 1}
\]

\[
\sigma(n) 
= \prod_{i=1}^{k} 
\frac{p_i^{\,a_i + 1} - 1}{p_i - 1}
\]

 

3. 최대공약수 (GCD)

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

 

유클리드 알고리즘

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

 

코드

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

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

 

베주 항등식

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