查找两个数字的GCD
在数学中，最大公约数(GCD)是最大可能的整数，该整数将两个整数相除。条件是数字必须为非零。
我们将遵循欧几里得算法来找到两个数字的GCD。
输入输出
Input: Two numbers 51 and 34 Output: The GCD is: 17
算法
findGCD(a, b)
输入：两个数字a和b。
输出：a和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