C代码: 最大公约数和最小公倍数
01 #from http://bbs.bccn.net/thread-224663-1-1.html
02 int GCD(int a, int b)
03 {
04 if(b == 0) return a;
05 else return GCD(b, a % b);
06 }
07
08 int LCM(int a, int b)
09 {
10 return a * b / GCD(a,b);
11 }
12
13 /*以下代码来自：http://en.wikipedia.org/wiki/Binary_GCD_algorithm */
14 unsigned int gcd(unsigned int u, unsigned int v)
15 {
16 int shift;
17
18 /* GCD(0,x) := x */
19 if (u == 0 || v == 0)
20 return u | v;
21
22 /* Let shift := lg K, where K is the greatest power of 2
23 dividing both u and v. */
24 for (shift = 0; ((u | v) & 1) == 0; ++shift) {
25 u >>= 1;
26 v >>= 1;
27 }
28
29 while ((u & 1) == 0)
30 u >>= 1;
31
32 /* From here on, u is always odd. */
33 do {
34 while ((v & 1) == 0) /* Loop X */
35 v >>= 1;
36
37 /* Now u and v are both odd, so diff(u, v) is even.
38 Let u = min(u, v), v = diff(u, v)/2. */
39 if (u < v) {
40 v -= u;
41 } else {
42 unsigned int diff = u - v;
43 u = v;
44 v = diff;
45 }
46 v >>= 1;
47 } while (v != 0);
48
49 return u << shift;
50 }