如何優化我的PrimeDivisor函數

我有找到素數的值的函數。（http://www.calculatorsoup.com/calculators/math/prime-factors.php）如何優化我的PrimeDivisor函數

例如，它需要12併產生2 * 2 * 3 = 2,3如果將需要10會產生2 * 5 = 2,5-那樣

我的代碼在低於：

public List<Integer> findPrimeDivisor(int value) { 

     ArrayList<Integer> divisors = new ArrayList<>(); 

     int startPoint = 2; 

     if (isRound(value, startPoint)) { 
      divisors.add(startPoint); 
     } 

     while (value != 1) { 
      if (isRound(value, startPoint)) { 
       value /= startPoint; 
       continue; 
      } 
      startPoint++; 
      divisors.add(startPoint); 
     } 

     return divisors; 
    } 

    private boolean isRound(int value, int roundBy) { 
     return (value % roundBy) == 0 ? true : false; 
    }

我該如何更有效地做到這一點？感謝您的建議:)

來源

2014-10-18 gokhan

谷歌「java分解」爲許多指針（包括許多在這個網站上）。 – NPE 2014-10-18 14:39:20

如果列舉了所有域的所有數量的所有主要因子（15？），那麼將無法更有效地做到這一點：一旦得到所需的效果，沒有其他算法或實現會更有效。效率 - 每個結果的努力 - 完全是另一回事;只是不要忘記適當地包括用戶和程序員的努力。在有效枚舉自然數的主要因子方面，最大的作用對我來說似乎是數學，其次是算法，然後是編碼 - 每個都有一個Stack Exchange站點。 – greybeard 2014-10-18 15:15:58

你的素數除數計算器不工作的原因有幾個，所以它不是很合乎邏輯的嘗試直接改進它。下面是一些原因：

不計算考生是否是質不是（這是關鍵）
從2號開始，並添加到結果集，如果不劃分值（你應該嘗試的對面）
一旦它終於發現了一些能分割的價值，它不的紅利添加到結果集（再次，你應該去的相反這裏）

如果您正在尋找找到它們的方法，您可以使用許多可用的庫中的一個，但如果您想開始製作自己的庫，我建議您從小處着手並將問題分成幾部分：

的方法找到素數（這應該緩存其結果）
的方法來嘗試所有邏輯上可能的候選人
一種方法，找到所有邏輯上可能的候選人

一個例子可能是：

public static void main(String[] args) 
{ 
    System.out.println(findPrimeDivisors(25)); 
    System.out.println(findPrimeDivisors(12)); 
    System.out.println(findPrimeDivisors(10)); 
    System.out.println(findPrimeDivisors(50)); 
} 

// Should be cached or maybe even hardcoded to a point 
public static boolean isPrime(int number) 
{ 
    for(int i = 2; i <= number/2; i++) 
     if(number % i == 0) 
      return false; 

    return true; 
} 

// Main loopbreaker, decides whether the next candidate should be tried or not, can be more efficient 
public static boolean tryNext(int candidate, int value) 
{ 
    return value/candidate >= 2; 
} 

public static List<Integer> findPrimeDivisors(int value) 
{ 
    List<Integer> resultList = new ArrayList<Integer>(); 

    int candidate = 2; 
    while(tryNext(candidate,value)) 
    { 
     if(isPrime(candidate) && (value % candidate == 0)) resultList.add(candidate); 
     candidate++; 
    } 

    return resultList; 
}

來源

2014-10-18 15:00:16 Pumpkin

感謝您的幫助，我瞭解我的錯誤 – gokhan 2014-10-18 15:16:59

如何優化我的PrimeDivisor函數

回答

相關問題