更相减损术
更相减损术
第一步：任意给定两个正整数；
判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。
继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是公约数。
求“等数”的办法是“更相减损”法。
第一步：任意给定两个正整数；
判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。
继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是公约数。
求“等数”的办法是“更相减损”法。
#include <stdio.h>
int main()
{
int a,b;
int ads=1; //为求最大公约数定初值
scanf("%d%d",&a,&b);
while(a%2==0&&b%2==0)
{
a/=2;b/=2;
ads*=2; //把a,b中的2^n都提出来
}
while(a!=b) //直到a和b相等
{ //也可理解为直到所得的 减数 与 差 相等为止
if(a>b) a-=b;
else b-=a;
}
ads*=a; //把最后一次循环所得减数 或者 差乘以前面的2^n
printf("%d",ads);
return 0;
}
int main()
{
int a,b;
int ads=1; //为求最大公约数定初值
scanf("%d%d",&a,&b);
while(a%2==0&&b%2==0)
{
a/=2;b/=2;
ads*=2; //把a,b中的2^n都提出来
}
while(a!=b) //直到a和b相等
{ //也可理解为直到所得的 减数 与 差 相等为止
if(a>b) a-=b;
else b-=a;
}
ads*=a; //把最后一次循环所得减数 或者 差乘以前面的2^n
printf("%d",ads);
return 0;
}
锐捷网络股份有限公司公司福利 349人发布
投递美团等公司10个岗位 >