最大公约数 C/C++

最大公约数的几种求法:

1.方法一利用循环求出最大公约数,效率最慢
[cpp]
#include <iostream>
using namespace std;
int main()
{
int a,b,i,d,record;
cin>>a>>b;
d=a>b?b:a;
for(i=1;i<=d;i++)
{
if(a%i==0&&b%i==0)
record=i;
}
cout<<record<<endl;
return 0;
}
[/cpp]

2.方法二递归欧几里得算法,效率较循环慢
[cpp]

#include <iostream>
using namespace std;
int gcd(int a,int b)
{
if(a==0) return b;
else return b==0?a:gcd(b,a%b);
}
int main()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
return 0;
}

[/cpp]

3.方法三循环欧几里德算法,效率高
[cpp]

#include <iostream>
using namespace std;
int gcd(int a,int b)
{
int c;
if(a==0) return b;
while(b!=0) {c=b;b=a%b;a=c;}
return a;
}
int main()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
return 0;
}

[/cpp]