首页 > 代码库 > 更相减损术求最大公约数-C

更相减损术求最大公约数-C

可参照辗转相除

 1 #include<stdio.h> 2  3 int main(void) 4 { 5     int x=260; 6     int y=104; 7  8     int temp;   //临时变量 9 10     int index=0;11     while((x%2==0)&&(y%2==0))12     {13         x/=2;14         y/=2;15         ++index;16     }17 18     while(x!=y)19     {20         temp=x-y;21         if(temp<y)22         {23             x=y;24             y=temp;25         }26         else27         {28             x=temp;29         }30     }31 32     while(index)33     {34         x*=2;35         --index;36     }37     printf("%d\n",x);38     return 0;39 }

也可以去掉减半的操作,这里严格按照定义使用。

更相减损术求最大公约数-C