[ Algorithm in Java ] 數、運算 : 最大公因數、最小公倍數、因式分解

轉載自 這裡
說明 :
最大公因數(GCD)可以使用輾轉相除法來求，最小公倍數(LCM)則由這個公式來求 : 

GCD * LCM = 兩數乘積

而因式分解則涉及質數表的建立, 可以參考 Eratosthenes 篩選求質數

解法 :
最大公因數可以使用輾轉相除法求解, 而因式分解需求出小於該數的所有質數，並試試看是不是可以整除並將可以整除的質數列入因數表裡.

實作 :
- 最大公因數/最小公倍數
透過輾轉相除法求出最大公因數, 再透過最大公因數求最小公倍數 :

- GCDPNumber.java :

view plaincopy to clipboardprint?

1. package alg.maths;  
2.   
3. public class GCDPNumber {  
4.     public static int gcd(int m, int n)  
5.     {  
6.         if(n==0) return m;   
7.         else return gcd(n, m%n);  
8.     }  
9.       
10.     public static int lcm(int m, int n){return m*n/gcd(m,n);}  
11.       
12.     public static void main(String[] args) {  
13.         System.out.println("GCD of (10, 4) = " + gcd(10, 4));  
14.         System.out.println("LCM of (10, 4) = " + lcm(10, 4));  
15.     }  
16. }  

- 因數分解
這裡透過類別 Prime 求出某一數以內的所有質數表, 再透過類別 Factor 求出該數的質因數分解.

- Prime.java :

view plaincopy to clipboardprint?

1. package alg.maths;  
2.   
3. import java.util.ArrayList;  
4. import java.util.List;  
5.   
6. public class Prime {  
7.     public static List findPrimes(int n)  
8.     {  
9.         List pml = new ArrayList();  
10.         boolean pm[] = new boolean[n+1];  
11.         for(int i=0; itrue;  
12.         int j=0;  
13.         for(int i=2; i
14.         {  
15.             if(pm[i])  
16.             {  
17.                 j=2;  
18.                 while((j*i)<=n)  
19.                 {  
20.                     pm[j*i] = false;  
21.                     j++;  
22.                 }  
23.             }  
24.         }  
25.         for(int i=2; iif(pm[i]) pml.add(i);  
26.         return pml;  
27.     }  
28. }  

- Factor.java :

view plaincopy to clipboardprint?

1. package alg.maths;  
2.   
3. import java.util.ArrayList;  
4. import java.util.List;  
5.   
6. public class Factor {  
7.     public static List factor(int n) {  
8.         int num = n;  
9.         List primes = Prime.findPrimes(num);  
10.         List list = new ArrayList();  
11.         for(int i = 0; primes.get(i) <= Math.sqrt(num);) {   
12.             if(num % primes.get(i) == 0) {   
13.                 list.add(primes.get(i));  
14.                 num /= primes.get(i);   
15.             }   
16.             else {  
17.                 i++;   
18.             }  
19.         }   
20.         list.add(num);        
21.         return list;  
22.     }  
23.       
24.     public static void main(String[] args) {  
25.         for(Integer f : Factor.factor(100)) {  
26.             System.out.print(f + " ");  
27.         }  
28.     }  
29. }