Javaの素因数分解

Question

私は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のように）繰り返し要因を考慮する必要があります。そして、私はこれを持っています。完全にリストラすることなく、どうすればいいですか？

Answer 1

ファクタとそのカウントを維持し、最終的には反復要因を説明できる別のコレクションを持つことができます。カウントを持つ地図が私の選択です。

Answer 2

私はあなたが最初からやり直し、そしてこの簡単な説明からアルゴリズムを構築すべきだと思う：

• 以下からこのリストを実行する2^16
• に等しい素数のList<Integer>を準備しますそれぞれの素数を候補除数として順番に試してください。
• 作業の除数に遭遇するたびに、それを分けることができなくなるまで、連続して除算します。次の素数に進む
• 素数のリストの終わりに達すると、1に等しくない限り、残りの数も同様に出力されます。

素数のリストを見つけること自体は楽しい問題です。 Dijkstraは1972年にそれについて魅力的な章を書きました。This articleにはC++の実装ととても面白い議論があります。

Answer 3

（1）if(c == 0 || i == 2)が間違っていると、a == 5の場合も2が印刷されます。

（2）コード（*）を変更せずに求めていることを実行するには、各素因数がその数で分けられる回数を数えます。それは単にあなたのprint文の前に[擬似コード]新しいループを追加することによって行うことができます。このループの最後で

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の提案を再設計に取り掛かります。