C語言求最大公約數和最小公倍數

C語言求最大公約數和最小公倍數，下面一起來看看吧。

操作方法

（01）思路：這是一個很基本的問題，最常見的就是兩種方法，輾轉相除法和輾轉相減法。通式分別為 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0)。根據通式寫出算法不難，這裏就不給出了。這裏給出《編程之美》上的算法，主要是為了減少迭代的次數。 對於x和y，如果y = k * y1, x= k * x1，那麼f(x, y) = k * f(x1, y1)。另外，如果x = p * x1，假設p為素數，並且y % p != 0，那麼f(x, y) = f(p * x1, y) = f(x1, y)。取p = 2。

（02）//函數功能: 求最大公約數 //函數參數: x,y為兩個數 //返回值: 最大公約數 int gcd_solution1(int x, int y) { if(y == 0) return x; else if(x < y) return gcd_solution1(y, x); else { if(x&1) //x是奇數 { if(y&1) //y是奇數 return gcd_solution1(y, x-y); else //y是偶數 return gcd_solution1(x, y>>1); } else //x是偶數 { if(y&1) //y是奇數 return gcd_solution1(x>>1, y); else //y是偶數 return gcd_solution1(x>>1, y>>1) << 1; } } }

（03）求最小公倍數：最常用的是輾轉相除法，有兩整數a和b：① a%b得餘數c② 若c=0，則b即為兩數的最大公約數③ 若c≠0，則a=b，b=c，再回去執行①

（04）int gcd_solution2(int x, int y) { int result = 1; while(y) { int t = x; if(x&1) { if(y&1) { x = y; y = t % y; } else y >>= 1; } else { if(y&1) x >>= 1; else { x >>= 1; y >>= 1; result <<= 1; } } } return result * x; }