수학에서 최대 공약수(GCD)는 두 정수를 모두 나누는 가능한 가장 큰 정수입니다. 조건은 숫자가 0이 아니어야 한다는 것입니다.
유클리드 알고리즘을 따라 두 숫자의 GCD를 찾습니다.
입력 및 출력
Input: Two numbers 51 and 34 Output: The GCD is: 17
알고리즘
findGCD(a, b)
입력: 두 개의 숫자와 b.
출력: 및 b의 GCD.
Begin if a = 0 OR b = 0, then return 0 if a = b, then return b if a > b, then return findGCD(a-b, b) else return findGCD(a, b-a) End
예
#include<iostream> using namespace std; int findGCD(int a, int b) { //assume a is greater than b if(a == 0 || b == 0) return 0; //as a and b are 0, the greatest divisior is also 0 if(a==b) return b; //when both numbers are same if(a>b) return findGCD(a-b, b); else return findGCD(a, b-a); } int main() { int a, b; cout << "Enter Two numbers to find GCD: "; cin >> a >> b; cout << "The GCD is: " << findGCD(a,b); }
출력
Enter Two numbers to find GCD: 51 34 The GCD is: 17