扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
其实我们可以用一个非常好理解的方法来做——辗转相除法。什么是辗转相除法？它是一个循环的过程，我们设a为被除数，b为除数，每一次将当前的除数作为下一次循环的被除数，将a除以b的余数作为下一次循环的除数，这样一直循环下去，直到除数等于0才停止。这时，被除数就是大公因数。
举个例子
求24,9的大公因数：
24/9=2......6
这时我们以9为下一轮的被除数，6为下一轮的除数。
9/6=1......3
我们再以6为下一轮的被除数，3为下一轮的除数。
6/3=2......0
我们再以3为下一轮的被除数，0为下一轮的除数。
可是除数为0了，不能再循环下去了。这时，3就是24和9的大因数。
c++代码在这里我们有两种方法来实现。
第一种：递归实现。
#includeusing namespace std;
int f(int a,int b)
{
if(b==0)return a; //当除数b为0时，a就是大公因数
return f(b,a%b);
}
int main()
{
int a,b;
cin>>a>>b; //a为被除数，b为除数
cout< 第二种：循环实现
#includeusing namespace std;
int main()
{
int a,b;
cin>>a>>b; //a为被除数，b为除数
while(b>0)
{
int t=a; //保存被除数的值
a=b; //除数b变成被除数a
b=t%b; //注意，a的值已经变了，只能用t来除以b
}
cout< 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网