最大公因數和最小公倍數

一丶 最大公因數求法：

      輾轉相除法(也稱歐幾裡得算法)原理:

二丶最小公倍數求法：兩個整數的最小公倍數等于兩整數之積除以最大公約數

1 #include <iostream>
 2  
 3 using namespace std;
 4  
 5 //輾轉相除法(歐幾裡得算法)
 6  
 7 int gcd(int a, int b)
 8 {
 9     int da = max(a,b);
10     int xiao = min(a,b);
11     if(da % xiao == 0)
12         return xiao;
13     else   
14     return gcd(xiao, da % xiao);
15  
16 }
17  
18 // 兩個整數的最小公倍數等于兩整數之積除以最大公約數
19  
20 int lcm(int a, int b)
21 {
22     return a*b / gcd(a, b);
23 }
24  
25 int main()
26 {
27     int x, y;
28     cout << "輸入兩個數字(按Ctrl+Z結束輸入): ";
29     while(cin >> x >> y)
30     cout << "這兩個數的最大公因數是：" << gcd(x, y) << endl
31              << "這兩個數的最小公倍數是：" << lcm(x, y) << endl;
32 }