2019/12/22 (1) 썸네일형 리스트형 최대공약수와 최소공배수 최대공약수 최대공약수를 구하는 알고리즘으로 유명한 유클리드 호제법이 있습니다. "두 개의 자연수 a, b에서 a를 b로 나눈 나머지 r이 있을 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다." 이 원리를 이용하여 a, b가 있을 때 b MOD r를 구하고 이를 r'라고 하면, r MOD r'를 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다. (gcd) 그대로 코드로 표현해보면 int gcd(int a, int b) { int r; while(b) { r = a % b; a = b; b = r; } return a; } 단, a > b는 이어야하기 때문에 b > a라면 두 숫자를 바꿔주는 과정이 필요합니다. int gcd(int a, int b) { if(b > a) .. 이전 1 다음
