577
Java求最大公約數與最小公倍數
如果數a能被數b整除，a就叫做b的倍數，b就叫做作a的約數．約數和倍數都表示一個數與另一個數的關係，不能單獨存在．如隻能說16是某數的倍數，2是某數的約數，而不能孤立地說16是倍數，2是約數．“倍”與“倍數”是不同的兩個概念，“倍”是指兩個數相除的商，它可以是整數、小數或者分數．“倍數”隻是在數的整除範圍內，相對於“約數”而言的一個數字概念，表示的是能被某一個自然數整除的數，它必須是一個自然數．
（1）最大公約數
最大公約數：幾個自然數公有的約數，叫做這幾個數的公約數；其中最大的一個，叫做這幾個數的最大公約數。
例如：12，16的公約數有1，2，4，其中最大的一個是4，4是12與16的最大公約數，一般記為（12，16）=4．12，15，18的最大公約數是3，記為（12，15，18）=3．
常用的求最大公約數的方法是短除法和分解質因數法．
短除法：開始時用觀察比較的方法，即：先把每個數的約數找出來，然後再找出公約數，最後在公約數中找出最大公約數。
例如：求12與18的最大公約數。
短除法例題
12的約數有：1、2、3、4、6、12。
18的約數有：1、2、3、6、9、18。
12與18的公約數有：1、2、3、6。
12與18的最大公約數是6。
這種方法對求兩個以上數的最大公約數，特別是數目較大的數，顯然是不方便的。於是又采用了給每個數分別分解質因數的方法。
分解質因數法：把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數．例如，求24和60的最大公約數．24=2×2×2×3，60=2×2×3×5，24與60的全部公有的質因數是2，2和3，它們的積是2×2×3=12，所以（24，60）=12．
除了這兩種方法外，還有一種輾轉相除法：
在數學中，輾轉相除法，又稱歐幾裏得算法，是求最大公約數的算法。
兩個數求最大公約數，可以用輾轉相除法。始終用較大數（被除數）除以較小數（除數），然後用除數代替較大數（被除數），餘數代替較小數（除數），代替完後繼續讓新的被除數除以除數。直到相除餘數為0時。最後的除數就是最大公約數。舉例：
222 407求最大公約數：
222 407（407除以222餘數185)
222 185(222除以185餘數37)
37 185（185除以37餘數0）
所以最大公約數為37
39 24求最大公約數
39 24（39/24，餘數15）
15 24（24/15，餘數9）
15 9（15/9，餘數6）
6 9（9/6，餘數3）
6 3（6/3，餘數0)
所以最大公約數為3
輾轉相除法可以用來計算兩個自然數的最大公約數，那若要計算多個自然數的最大公約數呢？
答：求幾個自然數的最大公約數，可以先求出其中兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數，依次求下去，直到最後一個為止。最後所得的那個最大公約數，就是所求的幾個數的最大公約數。 （求多個數的最小公倍數時也是同樣的道理）
（2）最小公倍數
最小公倍數：幾個數公有的倍數叫做這幾個數的公倍數，其中最小的一個叫做這幾個數的最小公倍數。數學上常用方括號表示。如[12，18，20]即12、18和20的最小公倍數。
最小公倍數的求法：
求幾個自然數的最小公倍數，同樣也可以采用分解質因數法和短除法
<1> 分解質因數法：先把這幾個數分解質因數，再把它們一切公有的質因數和其中幾個數公有的質因數以及每個數的獨有的質因數全部連乘起來，所得的積就是它們的最小公倍數。
例如，求[12，18，20]，因為12=2^2×3，18=2×3^2，20=2^2×5，其中三個數的公有的質因數為2，兩個數的公有質因數為2與3，每個數獨有的質因數為5與3，所以，[12，18，20]=2^2×3^2×5=180。
<2> 短除法：
其實隻要求出了最大公約數就能直接求最小公倍數了。可利用下麵這條公式
兩個數相乘等於這兩個數的最大公約數和最小公倍數的積。
java案例：
《1》求兩個數的最大公約數和最小公倍數(杭電ACM--1108有類似的題)
解法：用輾轉相除法先求出最大公約數，再通過公式：兩個數相乘等於這兩個數的最大公約數和最小公倍數的積。求出最小公倍數
代碼如下：
import java.util.Scanner;
public class Test1018 {
//求最大公約數
public static int commonDivisor(int n,int m){
//輾轉相除是用大的除以小的。如果n<m，第一次相當n與m值交換
while(n%m!=0){
int temp=n%m;
n=m;
m=temp;
}
return m;
}
//求最小公倍數
public static int commonMultiple(int n,int m){
return n*m/commonDivisor(n,m);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
System.out.println(commonMultiple(n,m));
System.out.println(commonDivisor(n,m));
}
}
《2》根據用戶輸入的個數，求出這些數的最小公倍數，以杭電ACM--2028為例
Lowest Common Multiple Plus
Problem Description
求n個數的最小公倍數。
Input
輸入包含多個測試實例，每個測試實例的開始是一個正整數n，然後是n個正整數。
Output
為每組測試數據輸出它們的最小公倍數，每個測試實例的輸出占一行。你可以假設最後的輸出是一個32位的整數。
Sample Input
2 4 6
3 2 5 7
Sample Output
12
70
代碼如下：
import java.util.Scanner;
public class Test2028 {
//求兩個最大公約數
public static long commonDivisor(long n,long m){
//輾轉相除是用大的除以小的。如果n<m，第一次相當n與m值交換
while(n%m!=0){
long temp=n%m;
n=m;
m=temp;
}
return m;
}
//求兩個數最小公倍數
public static long commonMultiple(long n,long m){
return n*m/commonDivisor(n,m);
}
//求多個數的最小公倍數
public static long commonMultiple(long[] a){
long value=a[0];
for(int i=1;i<a.length;i++){
value=commonMultiple(value,a[i]);
}
return value;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
long[] a=new long[n];
for(int i=0;i<a.length;i++){
a[i]=sc.nextLong();
}
System.out.println(commonMultiple(a));
}
}
}
最後更新：2017-04-02 22:16:39