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

標籤

2011年10月3日 星期一

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


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

GCD * LCM = 兩數乘積

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

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

實作 :
- 最大公因數/最小公倍數
透過輾轉相除法求出最大公因數, 再透過最大公因數求最小公倍數 :
- GCDPNumber.java :
  1. package alg.maths;  
  2.   
  3. public class GCDPNumber {  
  4.     public static int gcd(int m, int n)  
  5.     {  
  6.         if(n==0return 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(104));  
  14.         System.out.println("LCM of (10, 4) = " + lcm(104));  
  15.     }  
  16. }  

- 因數分解
這裡透過類別 Prime 求出某一數以內的所有質數表, 再透過類別 Factor 求出該數的質因數分解.
- Prime.java :
  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 :
  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. }  

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!