目錄
一、最大公約數
1、列舉法
2、輾轉相除法
二、最小公倍數
1、列舉法
2、擴大法
Hello，大家好，我是灰小猿，一個超會寫bug的程式猿，
今天在這里記錄一下在程式中求解兩個數的最大公約數和最小公倍數的幾種方法，
一、最大公約數
1、列舉法
采用列舉法求解兩個數的最大公約數是我們最常使用到的方法，兩個整數的最大公約數為a，則a應該是大于等于1，小于等于這兩個數的最小數的，因此我們可以在該范圍內對可能的數進行列舉即可，
使用程式如下：
/**
* 列舉法
* 求兩個數的最大公約數
* */
static public int gcd1(int a,int b) {
int ans = 1;
int min = Math.min(a, b);
for (int i = 1; i <= min; i++) {
if (a%i==0&&b%i==0) {
ans = i;
}
}
return ans;
}2、輾轉相除法
輾轉相除法是在數學中求解兩個數的最大公約數的方法，
思路是：
1、大數除以小數，如果余數是0，那么最大公約數就是這個小數，
2、否則繼續使用小數對得到的余數求余，直到余數為0，則結果等于最后的那個除數
程式如下：
/**
* 輾轉相除法
* 求兩個數的最大公約數
* */
static public int gcd2(int a,int b) {
if (a%b==0) {
return b;
}
return gcd2(b, a%b);
}二、最小公倍數
1、列舉法
采用列舉法求解兩個數的最小公倍數的方法：最小公倍數的最小可能是這兩個數的最大數，因此我們利用for回圈從該最大數開始遞增，直到找到第一個可以將這兩個數除盡的數即可，程式如下：
/**
* 列舉法
* 求兩個數的最小公倍數
* */
static public int lcm1(int a,int b) {
int max = Math.max(a, b);
for (int i = max; i <= a*b; i++) {
if (i%a==0&&i%b==0) {
max = i;
break;
}
}
return max;
}2、擴大法
擴大法其實也是列舉法的一種，只不過在for回圈上效率高于第一種列舉法，我們在進行for回圈時，是將較大數依次遞增2倍、3倍...，直到找到第一個可以將這兩個數除盡的數即可，程式如下：
/**
* 擴大法
* 求兩個數的最小公倍數
* */
static public int lcm2(int a,int b) {
int max = Math.max(a, b);
for (int i = max; i <= a*b; i+=max) {
if (i%a==0&&i%b==0) {
max = i;
break;
}
}
return max;
}
關于求解最大公約數和最小公倍數的方法，之后還會繼續更新效率更高的演算法，
有問題的小伙伴也可以提出優化，
覺得不錯記得點贊關注喲！
灰小猿陪你一起進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/256413.html
標籤：其他
下一篇：Web全堆疊~28.網路編程