1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <stdio.h>
#include <stdlib.h>
static int GreatestCommonDivisor(int a,int b)
{
int big=a>b?a:b;
int small=a<b?a:b;
int i;
for(i=small;i>1;i--)
{
if(big%i ==0 && small%i==0)
{
return i;
}
}
return 0;
}
static int GreatestCommonDivisor_2(int a,int b)
{
int big=a>b?a:b;
int small=a<b?a:b;
if(big%small==0)
{
return small;
}
return GreatestCommonDivisor_2(big%small,small);
}
static int GreatestCommonDivisor_3(int a,int b)
{
if(a==b)
{
return a;
}
int big=a>b?a:b;
int small=a<b?a:b;
return GreatestCommonDivisor_3(big-small,small);
}
static int gcd(int a, int b)
{
if(a == b)
{
return a;
}
if((a&1)==0 && (b&1)==0)
{
return gcd(a>>1, b>>1)<<1;
}
else if((a&1)==0 && (b&1)!=0)
{
return gcd(a>>1, b);
}
else if((a&1)!=0 && (b&1)==0)
{
return gcd(a, b>>1);
}
else
{
int big = a>b ? a:b;
int small = a<b ? a:b;
return gcd(big-small, small);
}
}
int main(int argc,char **argv)
{
if(argc!=3)
{
printf("argc count error\n");
return 0;
}
int com;
int a=atoi(argv[1]),b=atoi(argv[2]);
printf("a=%d,b=%d\n",a,b);
com=GreatestCommonDivisor(a,b);
printf("%d\n",com);
com=GreatestCommonDivisor_2(a,b);
printf("%d\n",com);
com=GreatestCommonDivisor_3(a,b);
printf("%d\n",com);
com=gcd(a,b);
printf("%d\n",com);
return 0;
}
|