최대공약수 썸네일형 리스트형 유클리드 알고리즘 (Euclid’s algorithm) 유클리드 알고리즘 (혹은 유클리드 호제법)이란? 두 양의 정수 A, B에 대한 최대공약수를 구하는 알고리즘이다. 이는 O(log N) 으로 가장 효율적으로 GCD를 구한다. * 최대공약수(Greatest common divisor, GCD)란, A, B를 나누는 자연수 중에서 가장 큰 자연수를 말한다. * 호제법이란, 두 수가 서로 상대의 수를 나누어 원하는 수를 얻는 알고리즘을 말한다. 최대공약수는 다음과 같은 성질을 갖는다. 식에서 mod는 나머지를 구하는 모듈러 연산(%) 이다. 성질을 이용한 예시는 다음과 같다. 다음은 C++로 구현한 코드이다. int gcd(int a, int b) { if (b > 0) return gcd(b, a % b); return a; } 더보기 이전 1 다음
