辗转相除法求最大公约数

admin

很经典的算法。小学老师讲的最大公约数一般用短除法，要经过很多次的试除，在c++里面实现并不容易，我们在这里使用辗转相除法。
设求a b两数的最大公约数，a=80,b=48，实际上等价于求b(=48)和 a%b(=32) 的最大公约数，直到a%b=0,这个是最大公约数就是b

1. #include <iostream>
   
2. using namespace std;
   
3. int a,b,c;
   
4. int main()
   
5. {
   
6.     cin>>a>>b;
   
7.     c=a%b;
   
8.     while (c!=0)
   
9.     {
   
10.         a=b;b=c;c=a%b;
    
11.     }
    
12.     cout<<b;
    
13. }
    

复制代码

高歌岭

1. #include<iostream>
   
2. using namespace std;
   
3. int a,b,c;
   
4. int main()
   
5. {
   
6.     cin>>a>>b;
   
7.     while(b>0)
   
8.     {
   
9.         c=a;
   
10.         a=b;
    
11.         b=c%b;
    
12.     }
    
13.     cout<<a;
    
14.     return 0;
    
15. }
    

复制代码

admin

楼上的做法感觉有问题！

JASONZHU

1. #include<iostream>
   
2. using namespace std;
   
3. int a,b,s;
   
4. int main()
   
5. {
   
6.     cin>>a>>b;
   
7.     s=a%b;
   
8.     while(s!=0)
   
9.     {
   
10.         a=b;
    
11.         b=s;
    
12.         s=a%b;
    
13.     }
    
14.     cout<<b;
    
15.     return 0;
    
16. }
    

复制代码