목록최대 공약수 최소공배수 알고리즘 (1)

hahn

[대수학 - 정수론] 유클리드 호제법에 대하여

유클리드 호제법이란? 유클리드 호제법(Euclidean Algorithm)은 유클리드 알고리즘이라고도 불리며, 2개의 자연수(다항식)의 최대공약수를 구하는 방법이다. 유클리드 호제법의 정리를 보면 a와 b가 자연수이고, a를 b로 나눈 나머지를 r이라고 하자. (단, a ≥ b, 0 ≤ r < b) a와 b의 최대공약수를 (a, b)라고 하면, (a, b) = (b, r)이 성립한다. 이해 일단 최대 공약수에 대한 이해가 필요하다. 최대 공약수라 함은 두 수를 모두 나누어 떨어지게 하는 수 중 가장 큰 수를 의미한다. (공약수 중 가장 큰 수) ex. 108 = 2 × 2 × 3 × 3 × 3 72 = 2 × 2 × 2 × 3 × 3 공통되는 부분을 골라내면 2 × 2 × 3 × 3이 된다. 즉 36이 ..
코딩테스트 연습/알고리즘 2021. 9. 17. 19:03
이전 Prev 1 Next 다음