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

1. 약수

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

 

2. 소인수

• 소수인 약수​

 

소인수분해

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

• 합성수를 소인수들의 곱으로 나타낸 것

 

약수의 합

\[
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}
\]

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

 

3. 최대공약수 (GCD)

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

 

베주 항등식

\[
ax + by = \gcd(a, b)
\]

• 두 정수의 최대공약수를 원래 두 수의 배수의 합으로 나타낼 수 있음
• ✅ 위 식을 만족하는 정수 x, y쌍이 항상 존재함 (여러개 존재. 공집합 아님)

 

유클리드 알고리즘

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

 

코드

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

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

 

출처

• Wiki - 베주 항등식