Java中的素因子分解

我正在研究Java中的素數因子分解程序，該程序顯示數字的所有素數因子，即使它們重複。我有這個：Java中的素因子分解

public static void factors(int a) 
{ 
    int c=1; 
    for(int i = 1; i <= a;i++) 
    { 
     if(a%i == 0) 
     { 
      for(int k = 2; k < i; k++) 
      { 
       if(i%k == 0) 
       { 
        c = 1; 
        break; 
       } 
       else 
       { 
        c = 0; 
       } 
      } 
      if(c == 0 || i == 2) 
      { 
       System.out.print(i+ ", "); 
      } 
     } 
    } 
}

我需要考慮重複因素（如8,2,2,2）。我怎麼能沒有完全重組呢？

來源

2012-03-24 Daniel Horowitz

繼續分解因素，直到你不能再分裂。這些因素是否重複都沒有關係。 – 2012-03-24 19:21:20

你確定你的問題需求被正確理解。通常，你要麼列出所有因素（所以12將是1,2,3,4,6,12）或者你分解因子（所以12將是2,2,3）。你似乎試圖做的事情是奇怪的。 – 2012-03-24 19:24:58

這是功課嗎？如果是，請標記問題。另外，你是什麼意思*「沒有完全重組」*？ – sch 2012-03-24 19:32:32

您可以擁有另一個保存因子及其數量的集合，並且可以最終考慮重複的因素。有計數的地圖將是我的選擇。

來源

2012-03-24 19:25:50 tsatiz

我想你應該重新開始，並建立從這個簡單的描述的算法：

準備素數，通過這個列表從小於或等於2^16
運行的List<Integer>從低到高依次嘗試每個素數作爲候選除數
每次遇到一個工作的除數時，不斷地將其除數直到不能再用數除以它;然後繼續下一個素數
一旦到達素數列表的末尾，您的剩餘數字也應該打印，除非它等於1。

找到素數列表本身就是一個有趣的問題。 Dijkstra在1972年寫了一篇引人入勝的章節。This article有一個C++實現和一個非常好的討論。

來源

2012-03-24 19:28:57 dasblinkenlight

（1）if(c == 0 || i == 2)是錯誤的，它也會爲a == 5打印2。（2）爲了在不更改代碼（*）的情況下執行所要求的操作，您應該計算每個素數因子可以被數字分解多少次。它可以通過打印語句之前簡單地增加一個新的循環[僞代碼]來完成：

boolean b = true; 
int k = 1; 
while (b) { 
    if (a % (int) Math.pow(i, k+1) == 0) k++; 
    else b = false; 
}

在這個循環結束，k表示i多少次的a的一個主要因素。

（*）注意：儘管這種方法應該可行，但我仍然會按照@KerrekSB的建議去重新設計。

來源

2012-03-24 19:36:04 amit

Java中的素因子分解

回答

相關問題