질문이 조금 짧습니다. 어떤 두 수(또는 세 수)의 최대공약수(GCD)를 구하시려는 건가요? 예를 들어 “108과 30의 최대공약수”처럼 두 수를 알려주시면 바로 계산해 드립니다.
참고로 108 자체에 관한 정보는 아래와 같습니다.
- 소인수분해: 108 = 2^2 × 3^3
- 모든 약수(12개): 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108
- 108의 최댓값을 제외한 가장 큰 약수(최대 진약수): 54
최대공약수 구하는 방법(간단히)
- 소인수분해 방법: 두 수의 공통된 소인수의 최소 지수들을 곱함.
예) gcd(108, 30)
108 = 2^2 × 3^3
30 = 2^1 × 3^1 × 5^1
공통 소인수: 2^(min(2,1)) × 3^(min(3,1)) = 2^1 × 3^1 = 6 → gcd = 6
- 유클리드 알고리즘(나눗셈 반복):
예) gcd(108, 30)
108 = 30×3 + 18
30 = 18×1 + 12
18 = 12×1 + 6
12 = 6×2 + 0 → 마지막 나머지 6이 gcd
원하시면 계산할 다른 수(들)을 알려 주세요. 바로 최대공약수와 과정(소인수분해 또는 유클리드 알고리즘 단계별)을 보여 드리겠습니다.
참고 자료