/*第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;
若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。
继续这个操作,直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。*/
#include //用更相减损术计算最大公约数
#include
using namespace std;
int main (void)
{
int a;
int b;
int max;
int n=1;
printf("a=");
scanf ("%d",&a);
printf("b=");
scanf ("%d",&b);
for( n=2;a%2==0 && b%2==0;n+=2)
{
a=a/2;
b=b/2;
}
if (a<b)
{
max=b;
b=a;
a=max;
}
while(a!=b)
{
int c;
c=a-b;
a=b;
b=c;
}
printf ("最大公约数=%d",a*n);
return 0;
}
int main (void)
{
int a;
int b;
int max;
int n=1;
printf("a=");
scanf ("%d",&a);
printf("b=");
scanf ("%d",&b);
for(;a%2==0 && b%2==0;n*=2)//这里n是前面2的乘机,不是2的和
{
a=a/2;
b=b/2;
}
if (a<b)
{
max=b;
b=a;
a=max;
}
while(a!=b)
{
int c;
c=a-b;
if(b>c){//需要判断B和C的大小再做减法
a=b;
b=c;
}else{
a=c;
}
}
printf ("最大公约数=%d",a*n);
return 0;
}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。