最大公约数

 1 /*
 2     Name: 求最大公约数的三种方法 
 3     Copyright: 
 4     Author: 润青 
 5     Date: 01/11/18 10:57
 6     Description: 穷举法、辗转相除法、相减法 
 7 */
 8 #include<stdio.h>
 9 void gcd1(int m,int n);
10 void gcd2(int m,int n); 
11 void gcd3(int m,int n);  
12 int m,n; 
13 int main(){
14     int sum=10; 
15     while(sum--){
16         scanf("%d%d",&m,&n);
17         gcd1(m,n);
18         gcd2(m,n);
19         gcd3(m,n);
20     } 
21     
22     return 0; 
23 }
24 void gcd1(int m,int n){
25     //printf("穷举法

"); 
26     int min;
27     int mod1,mod2;
28     int count=0; 
29     if(m>=n)
30         min=n;
31     else
32         min=m;
33     while(1){
34         mod1=m%min;
35         mod2=n%min;
36         count++;
37         if(mod1==0&&mod2==0){
38             printf("最大公约数：%d
",min);
39             printf("count=%d
",count); 
40             break; 
41         } 
42         else{
43             min--;
44         }  
45     }
46 }
47 void gcd2(int m,int n){
48     //printf("辗转相除法

"); 
49     int max,min;
50     int count = 1; 
51     if(m>=n){
52         max=m;
53         min=n; 
54     } 
55     else{
56         max=n;
57         min=m; 
58     }
59       int mod=max%min;
60     while(mod!=0){
61         max=min;
62         min=mod;
63         mod=max%min; 
64         count++; 
65     }
66     printf("最大公约数：%d
",min);
67     printf("count=%d
",count); 
68 }
69 void gcd3(int m,int n){
70     //printf("相减法

"); 
71     int max,min;
72     int count = 1; 
73     if(m>=n){
74         max=m;
75         min=n; 
76     } 
77     else{
78         max=n;
79         min=m; 
80     }
81     int sub=max-min;
82     while(sub!=0){
83         if(min>=sub){
84             max=min;
85             min=sub; 
86         } 
87         else{
88             max=sub;
89             min=min; 
90         } 
91         sub=max-min;
92         count++; 
93     }
94     printf("最大公约数：%d
",min);
95     printf("count=%d
",count); 
96 }