유클리드 호제법 알고리즘

[알고리즘] 최대공약수와 최소공배수 - 간단하게 구현해보기 (+ 유클리드 호제법 알고리즘) (C++)

최대공약수란 무엇인가? 최대공약수는 초등학교 수학 시간에 배우는 내용으로, 아마 이 글을 보시는 여러분이라면 이미 아시겠지만, 그 개념을 한 번 더 짚고 넘어가보자. 쉬운 이해를 위해 실제 정의가 아닌 초등학교 교과서에 제시된 내용을 참고하였다. n의 약수 : n을 나누어 떨어지게 하는 수 a, b의 공약수 : a와 b의 공통된 약수 a, b의 최대공약수 : a와 b의 공통된 약수 중 가장 큰 수 이 개념을 이용하여 반복문으로 다음과 같이 최대공약수를 구하는 함수 코드를 쓸 수 있다. #include #include // 최대공약수를 계산하는 함수 long getBCD (long a, long b) { for(int div = min(a, b); div > 0; div--) { if((a % div ==..