GCD求最大公约数
最后更新于:2022-04-01 09:33:02
求最大公约数哪个强,果断GCD,非递归版本和递归版本如下:
~~~
#include<iostream>
using namespace std;
int gcd(int a, int b){ //非递归版本
int big = max(a, b);
int small = min(a, b);
int temp;
while(small != 0 ){
temp = big % small;
big = small;
small = temp;
}
return big;
}
int gcd_(int a, int b){//递归版本
int big = max(a, b);
int small = min(a, b);
int temp = big % small;
return temp == 0 ? small : gcd_(small, temp);
}
int main(){
int a = 34, b = 8;
cout<<gcd(a, b)<<endl;
cout<<gcd_(a, b)<<endl;
return 0;
}
//output:
// 2
// 2
~~~