資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式查詢最小公倍數
兩個數的最小公倍數 (LCM) 是這兩個數的倍數中最小的數。
例如：假設我們有以下兩個數：15 和 9。
15 = 5 * 3 9 = 3 * 3
因此，15 和 9 的最小公倍數是 45。
查詢兩個數的最小公倍數的程式如下所示：
示例
#include <iostream>
using namespace std;
int main() {
int a=7, b=5, lcm;
if(a>b)
lcm = a;
else
lcm = b;
while(1) {
if( lcm%a==0 && lcm%b==0 ) {
cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
break;
}
lcm++;
}
return 0;
}輸出
The LCM of 7 and 5 is 35
在上述程式中，變數 lcm 設定為兩個數中較大的一個。這透過以下程式碼片段演示。
if(a>b) lcm = a; else lcm = b;
此後，while迴圈執行。在這個迴圈中，如果 LCM 既能被 a 也能被 b 整除，那麼它就是這兩個數的最小公倍數，並顯示出來。如果不是，則遞增 LCM 直到滿足此條件。
解釋這一點的程式碼片段如下：
while(1) {
if( lcm%a==0 && lcm%b==0 ) {
cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
break;
}
lcm++;
}另一種查詢兩個數的最小公倍數的方法是使用最小公倍數和最大公約數公式。這個公式規定兩個數的乘積等於它們的最小公倍數和最大公約數的乘積。
a * b = GCD * LCM
使用該公式查詢兩個數的最小公倍數的程式如下所示：
示例
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a = 7, b = 5;
cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);
return 0;
}輸出
LCM of 7 and 5 is 35
在上述程式中，最小公倍數是使用公式計算的。首先，使用 gcd() 獲取 a 和 b 的最大公約數。這是一個遞迴函式。它有兩個引數，即 a 和 b。如果 b 大於 0，則將 a 返回到 main() 函式。否則，gcd() 函式將使用值 b 和 a%b 遞迴呼叫自身。
這透過以下程式碼片段演示。
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}獲得最大公約數後，使用公式計算最小公倍數。然後顯示出來。這在以下程式碼片段中顯示。
cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);
更新於：2020年6月24日
瀏覽量：1萬+
廣告