如何用C++求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)
原理
最大公約數(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)文章
C語言類型轉(zhuǎn)換與常量的細(xì)節(jié)深入理解探究
這篇文章主要為大家介紹了C?語言類型轉(zhuǎn)換與常量的細(xì)節(jié)深入理解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12C++詳細(xì)講解模擬實(shí)現(xiàn)位圖和布隆過濾器的方法
位圖(bitset)是一種常用的數(shù)據(jù)結(jié)構(gòu),常用在給一個(gè)很大范圍的數(shù),判斷其中的一個(gè)數(shù)是不是在其中。在索引、數(shù)據(jù)壓縮方面有很大的應(yīng)用。布隆過濾器是由布隆提出的,它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中2022-06-06詳解C語言中strcpy函數(shù)與memcpy函數(shù)的區(qū)別與實(shí)現(xiàn)
這篇文章主要介紹了C語言中字符串拷貝函數(shù)(strcpy)與內(nèi)存拷貝函數(shù)(memcpy)的不同及內(nèi)存拷貝函數(shù)的模擬實(shí)現(xiàn),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-12-12Linux中rm命令使用以及C/C++代碼實(shí)現(xiàn)
m 是remove 的縮寫,Linux中 rm 命令的功能為刪除一個(gè)目錄中的一個(gè)或多個(gè)文件或目錄,它也可以將某個(gè)目錄及其下的所有文件及子目錄均刪除,這篇文章主要給大家介紹了關(guān)于Linux中rm命令使用以及C/C++代碼實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下2022-04-04Qt使用windeployqt工具實(shí)現(xiàn)程序打包發(fā)布方法
本文主要介紹了Qt使用windeployqt工具實(shí)現(xiàn)程序打包發(fā)布方法,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-11-11C語言的fork函數(shù)在Linux中的進(jìn)程操作及相關(guān)面試題講解
fork函數(shù)只能在類Unix的系統(tǒng)中使用,用于創(chuàng)建子線程,這里總結(jié)了C語言的fork函數(shù)在Linux中的進(jìn)程操作及相關(guān)面試題講解,先來看一下C語言程序的存儲(chǔ)空間與進(jìn)程示意:2016-06-06簡(jiǎn)述C語言中system()函數(shù)與vfork()函數(shù)的使用方法
這篇文章主要介紹了簡(jiǎn)述C語言中system()函數(shù)與vfork()函數(shù)的使用方法,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-08-08