資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用歐幾里得演算法查詢兩個數字的最大公約數和最小公倍數的 Java 程式
歐幾里得演算法是一種有效的演算法，可以幫助我們找到兩個數字的最大公約數和最小公倍數。在本文中，我們將學習編寫一個 Java 程式，使用歐幾里得演算法找到兩個數字的最大公約數和最小公倍數。
兩個數字的最大公約數
最大公約數（GCD），也稱為最大公因數，是能夠精確地整除兩個給定數字的最高公因數。現在讓我們來看一個例子，並計算兩個數字的最大公約數。
因數 - 在數學中，因數是可以整除給定數字的數字。
例如 - 8 可以被 1、2、4、8 整除。因此，1、2、4、8 是 8 的因數。
示例
考慮數字 8 和 16
8 的因數是：1、2、4、8
16 的因數是：1、2、4、8、16
能整除 8 和 16 的公因數是 1、2、4、8。在這些公因數中，最大的公因數是 8。因此，8 是 8 和 16 的最大公約數。
兩個數字的最小公倍數
最小公倍數（LCM），也稱為最小公倍數，是可以被兩個給定數字整除的最小數字，即最小的公倍數。
倍數 - 在數學中，倍數是可以被給定數字整除的數字。
例如 - 8、16、24、32、... 可以被 8 整除。所以 8、16、24、32 是 8 的倍數。
示例
考慮數字：8 和 16
8 的倍數是 8、16、24、...
16 的倍數是 16、32、48、...
可以被 8 和 16 整除的公倍數是 16、32、48 等。這兩個數字的最小公倍數是 16。因此，16 是 8 和 16 的最小公倍數。
現在我們將實現一個程式，使用歐幾里得演算法找到兩個數字的最小公倍數和最大公約數，因為它是快速找到最小公倍數和最大公約數的有效方法。
歐幾里得演算法基於以下原理：
“如果 a>b 且 a、b 是兩個整數，則 a 和 b 的最大公約數與 b 和 a 除以 b 的餘數的最大公約數相同”。
歐幾里得演算法
讓我們將 a 和 b 視為兩個數字
如果b=0，則我們返回a作為這兩個數字的最大公約數。
否則，我們將a替換為b，將 b 替換為 a、b 的餘數，然後遞迴呼叫 GCD 函式。
找到最大公約數後，我們可以找到LCM(a, b) = (a*b) / GCD
示例
第一步是用較大的數字（36）除以較小的數字（24）並找到餘數。我們可以使用模運算子（%）來做到這一點。
36 % 24 = 12
餘數是 12。然後我們用較小的數字（24）除以餘數（12）並找到新的餘數。
24 % 12 = 0
餘數為 0，這意味著我們已經找到了 24 和 36 的最大公約數。最大公約數是最後一個非零餘數，即 12。
因此，24 和 36 的最大公約數是 12。我們可以透過檢查 12 是否是 24 和 36 的公約數，以及是否有更大的數字可以均勻地整除 24 和 36 來確認這一點。
LCM(24,36) = (24*36)/12 = 72。
24 和 36 的最小公倍數是 72。
演算法
初始化兩個數字。
編寫一個遞迴方法來查詢數字的最大公約數。
建立一個自定義類物件。
使用自定義類物件從主方法呼叫遞迴方法。然後使用最大公約數的值查詢數字的最小公倍數。
示例
在這個例子中，我們初始化兩個數字，然後建立一個 GCD 類的物件，並使用 GCD 類物件呼叫 GCD 方法，並將這兩個數字傳遞給方法並獲取 gcd 值並將其儲存。然後，我們透過將兩個數字相乘併除以 gcd 值來計算 lcm。然後我們列印這兩個數字的 lcm 和 gcd。
//Java Program to find G.C.D and L.C.M of two numbers using Euclid’s Algorithm
import java.util.*;
class Gcd{
public int GCD(int number1, int number2) {
if (number2 == 0) {
return number1;
}
return GCD(number2, number1 % number2);
}
}
public class Main {
public static void main(String[] args) {
int number_1 = 36;
int number_2 = 24;
Gcd gcdObject = new Gcd();
int gcd = gcdObject.GCD(number_1, number_2);
System.out.println("G.C.D of "+" "+number_1+" & "+number_2 +" is: "+gcd);
int lcm = (number_1 * number_2) / gcd;
System.out.println("L.C.M of "+" "+number_1+" & "+number_2 +" is: "+lcm);
}
}
輸出
G.C.D of 36 & 24 is: 12 L.C.M of 36 & 24 is: 72
因此，在這篇文章中，我們使用 Java 程式設計中的歐幾里得演算法計算了兩個數字的最大公約數和最小公倍數。
2K+ 次檢視
