欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

如何用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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論