최대 공약수(GCD)란?
최대 공약수(Greatest Common Divisor)는 두 수 이상의 자연수를 나누어 떨어지게 하는 가장 큰 수입니다. 예를 들어, 12와 18의 공약수는 1, 2, 3, 6이고, 이 중 가장 큰 수는 6입니다. 따라서 GCD(12,18) = 6 입니다.
최대공약수 구하는 법
- 약수 나열법: 모든 약수를 구해 공통으로 겹치는 가장 큰 수를 선택
- 소인수분해: 두 수를 소인수분해하여 공통된 소인수의 최소 지수를 곱함
- 유클리드 호제법:
gcd(a, b) = gcd(b, a % b)를 반복 적용
자바스크립트로 GCD 구하기
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
console.log(gcd(48, 18)); // 결과: 6최대 공약수 활용 예시
| 🧮 분수 기약분수 변환 | 분자와 분모를 GCD로 나누어 기약분수 만들기 |
|---|---|
| 🔗 최소공배수(LCM) 계산 | LCM(a,b) = (a × b) ÷ GCD(a,b) |
| 🔒 알고리즘·암호학 | RSA 등 암호 알고리즘에서 큰 수의 GCD 계산 활용 |