原理

最大公約數

有兩個數字n和m。現在要求兩個數字的最大公約數。

例如：n為18，m為4.

正常我們的思路求解最大公約數是暴力破解，遍歷一遍公約數，取最大的那個，但是這樣有一個問題，就是時間復雜度過高了。

有沒有什么優化的方法呢？

我們可以先把18變成18-4=14，然后求和4的最大公約數；以此往復。但是每次都需要遞減，碰到1000001和200這樣的數字時，時間復雜度還是很高。

所以我們需要有最優化的方法

我們可以把數字遞減理解為除以數字很多次，那么就變成了18對4取余，此時變為2和4；然后我們把4對2取余，此時變為2和0；那么最終結果就為2.

最小公倍數

通過觀察18和4兩個數字，發現18 = 2 * 9； 4 = 2 * 2；9和2都是質數，而2則是共同的最大公約數。

我們假設有兩個數字n和m。

n = k * a  -- 1式
m = k * b  -- 2式
那么gcd（n，m）=k.

所以我們把1式和2式相乘，左邊=n * m，右邊=k * k * a * b。

就得到n * m = gcd（n， m） * k * a * b

此時的a * b * k 正好式n和m的最小公倍數，所以就得到

n * m = gcd（n， m） *  lcm（n， m）

代碼

#include <iostream>

using namespace std;

//定義gcd求最大公約數的函數
int gcd(int num1, int num2) {
	if (num1 == num2) {
		return num1;
	}
	else if (num1 < num2) {
		return 	num1 == 0 ? num2 : gcd(num1, num2 % num1);
	}
	else {
		return gcd(num2, num1);
	}
}

// 定義最小公倍數的函數
int lcm(int num1, int num2) {
	return num1 / gcd(num1, num2) * num2;
}

int main() {
	int n, m;
	cout << "輸入兩個數字n和m：\n";
	cin >> n >> m;
	printf("%d和%d的最大公約數為%d \n", n, m, gcd(n, m));
	printf("%d和%d的最小公倍數為%d", n, m, lcm(n, m));
	return 0;
}

運行結果

補充：性質

1.最小公倍數是最大公因數的倍數（最小公倍數 / 最大公因數 = 一個整數）

2.a與b的和差是最大公因數的倍數

3.最大公因數一定小于或等于min(a,b)

4.最小公倍數一定大于或等于max(a,b)

5.a*b = 最小公倍數*最大公因數

6.如果a, b兩個數是互質數，最大公因數等于1，最小公倍數等于a*b

總結