常见
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int a,b,c;
while(1)
{
cout<< "输入两个数字求最大公约数"<<endl;
cin>>a>>b;
cout<<"最大公约数是";
cout<<gcd(a,b)<<endl;;
}
return 0;
}
相减法
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
while(1)
{
cout<< "输入两个数字求最大公约数"<<endl;
cin>>a>>b;
while(a!=b)
{
if(a>b)
a=a-b;
else
b=b-a;
}
cout<<"最大公约数是";
cout<<a<<endl;;
}
return 0;
}
穷举法
三个变量，a,b,c;
c=（a,b）两个变量中较小的那个。
然后a,b分别都与c相除，只要有一方不能被c整除，就继续循环，循环中c--，c逐次减少，直到a,b,都能同时被c整除，运行结束。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c;
while(1)
{
cout<< "输入两个数字求最大公约数"<<endl;
cin>>a>>b;
c=(a>b)?b:a;
while(a%c!=0||b%c!=0)
{
c--;
}
cout<<"最大公约数是";
cout<<c<<endl;;
}
return 0;
}
辗转相除法
1.将两整数求余 a%b = c
2.如果c = 0;则b为最大公约数
3.如果c != 0,则 a = b；b = c；继续从1开始执行
4.也就是说该循环的是否继续的判断条件就是c是否为0
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c;
while(1)
{
cout<< "输入两个数字求最大公约数"<<endl;
cin>>a>>b;
c=a%b;
while(c!=0)
{
a=b;
b=c;
c=a%b;
}
cout<<"最大公约数是";
cout<<b<<endl;;
}
return 0;
}