如何用C++求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)

更新時(shí)間：2023年01月05日 09:13:04 作者：Kinght_123

最大公約數(shù)是指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中,最大的一個(gè)約數(shù),常用的方法是歐幾里得算法,也叫輾轉(zhuǎn)相除法,下面這篇文章主要給大家介紹了關(guān)于如何用C++求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)的相關(guān)資料,需要的朋友可以參考下

原理

最大公約數(shù)

有兩個(gè)數(shù)字n和m?，F(xiàn)在要求兩個(gè)數(shù)字的最大公約數(shù)。

例如：n為18，m為4.

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

有沒有什么優(yōu)化的方法呢？

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

所以我們需要有最優(yōu)化的方法

我們可以把數(shù)字遞減理解為除以數(shù)字很多次，那么就變成了18對(duì)4取余，此時(shí)變?yōu)?和4；然后我們把4對(duì)2取余，此時(shí)變?yōu)?和0；那么最終結(jié)果就為2.

最小公倍數(shù)

通過觀察18和4兩個(gè)數(shù)字，發(fā)現(xiàn)18 = 2 * 9； 4 = 2 * 2；9和2都是質(zhì)數(shù)，而2則是共同的最大公約數(shù)。

我們假設(shè)有兩個(gè)數(shù)字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

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

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

代碼

#include <iostream>

using namespace std;

//定義gcd求最大公約數(shù)的函數(shù)
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);
	}
}

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

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

運(yùn)行結(jié)果

補(bǔ)充：性質(zhì)

1.最小公倍數(shù)是最大公因數(shù)的倍數(shù)（最小公倍數(shù) / 最大公因數(shù) = 一個(gè)整數(shù)）

2.a與b的和差是最大公因數(shù)的倍數(shù)

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

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

5.a*b = 最小公倍數(shù)*最大公因數(shù)

6.如果a, b兩個(gè)數(shù)是互質(zhì)數(shù)，最大公因數(shù)等于1，最小公倍數(shù)等于a*b

總結(jié)

到此這篇關(guān)于如何用C++求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)的文章就介紹到這了,更多相關(guān)C++求最大公約數(shù)和最小公倍數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: