1 #include <string.h>
2 #include <stdio.h>
3
4 int Gcd(int m, int n)
5 {
6 if (m < n) {
7 return Gcd(n, m);
8 }
9
10 if (n == 0) {
11 return m;
12 } else {
13 return Gcd(n, m % n);
14 }
15 }
16
17 int Gcd2(int m, int n)
18 {
19 if (m < n)
20 return Gcd2(n, m);
21
22 if (n == 0)
23 return m;
24 else
25 return Gcd2(m - n, n);
26 }
27
28 int Gcd3(int m, int n)
29 {
30 if (m < n)
31 return Gcd3(n, m);
32 if (n == 0)
33 return m;
34 if (m % 2 == 0 && n % 2 == 0)
35 return 2 * Gcd3(m / 2, n / 2);
36 if (m % 2 == 0)
37 return Gcd3(m / 2, n);
38 if (n % 2 == 0)
39 return Gcd3(m, n / 2);
40 return Gcd3(m - n, n);
41
42 }
43
44
45 int main()
46 {
47 printf("%3d\n", Gcd3(25,15));
48
49 return 0;
50 }