유클리드 호제법이란?
유클리드 호제법은 두수의 최대공약수를 구하기 위한 수학적 풀이입니다.
이방법은 매우 간단하면서도 효율적이며, 수학적으로도 정확합니다. 유클리드 호제법의 기본 아이디어는 두 수 a와 b의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수가 같다는 것입니다.
두수의 최대공약수를 유클리드 호제법을 사용해 풀게되면 두 수의 최소공배수 또한 쉽게 계산이 가능합니다.
유클리드 호제법의 알고리즘
두 양의 정수 a와 가 주어졌을 때, a > b 라고 가정합니다. 유클리드 호제법은 다음과 같이 진행됩니다
유클리드 호제법은 a b 크기가 어떻든 상관없이 적용된다!!
- 를 로 나누어 나머지 을 구합니다. 즉, r = a % b
- 만약 r = 0 이라면, 가 a와 b의 최대공약수입니다.
- r != 0 이라면, 와 의 최대공약수는 b와 r의 최대공약수와 같습니다.
- 즉, GCD(a, b) = GCD(b, r). (GCD = Greatest Common Divisor, 최대공약수이다.)
- 이 과정을 r = 0이 될 때까지 반복하면, 그때의 가 a와 의 최대공약수가 됩니다.
예제
예를 들어, a=252와 b=105가 주어졌을 때, 유클리드 호제법은 다음과 같이 진행됩니다:
- 252 mod 105=42
- 105 mod 42=21
- 42 mod 21=0
따라서 GCD(252,105)=21입니다.
최대공약수를 이용한 최소공배수 계산
두 수 a와 b의 최소공배수는 다음과 같이 구할 수 있습니다.
최소공배수(a,b) = |a x b| / 최대공약수(a,b) 로 구해볼 수 있다.
'게임 수학' 카테고리의 다른 글
내적의 응용 (0) | 2024.08.21 |
---|---|
내적 (0) | 2024.08.21 |
사원수(쿼터니온)이란? (0) | 2023.09.06 |
게임 수학 - 벡터의 사칙연산, 외적 (0) | 2023.07.20 |
게임 수학 - 회전 3장 / 회전 공식 (0) | 2023.07.20 |