0

整数の各素因数の数を数えたい。たとえば、18 = 2 ^ 1 * 3^2です。各素数のすべての指数部分を取得したいと思います。18番の場合、1 + 2=3です。
以下は、整数のすべての素因数を生成するプログラムです。

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for (int i = 2; i <= n / i; i++) {
        while (n % i == 0) {
            System.out.print(i + ", ");
            n /= i;
        }
    }
    if (n > 1)
        System.out.print(n + ", ");

入力18の場合、このプログラムは2、3、3、を出力します。要件を満たすために、各素因数の発生をカウントするには、最初にそれらすべてをリストに追加し、次にリストのfor開始から終了までのループで各数の発生をカウントできます。しかし、この考えは私には良くないようです。不必要なことforに、すべての素因数に対して1つのループを追加しています。これは、この素因数がリストにn回含まれていることを示しています。
整数の素因数の個々の数を取得するためのより良いアプローチ。

4

2 に答える 2

1

yy、@attila と @robert が言ったように:

import java.util.Scanner; 
import java.util.TreeMap; 

public class Test{
    public static void main( String args[] ){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeMap<Integer, Integer> factors = new TreeMap<Integer, Integer>(); 

        for (int i = 2; i <= n / i; i++) {
            int count = 0; 

            while (n % i == 0) {
                System.out.print(i + ", ");
                n /= i;
                count ++; 
            }
            if( count > 0 ) 
                factors.put( i, count ); 
        }
        if (n > 1){
            System.out.print(n + ", ");
            factors.put( n, 1 ); 
        }
        System.out.println(); 

        System.out.println( "-------------" ); 
        for( Integer factor : factors.keySet() ){
            System.out.println( factor + "^" + factors.get( factor ) ); 
        }
    }
}

要素を自然な順序で保持しているため、ツリーマップを使用しています。これはきれいです:)少し高速なハッシュマップを使用することもできます。しかし、素数分解の実装は非常に遅いため、それほど重要ではないと思います:)

于 2012-04-12T16:05:34.700 に答える
0

を実行するたびn/=i;に、要因に遭遇します。したがって、その時点で (0 から開始して) カウンターをインクリメントすることにより、因数分解プロセスの最後に因数の総数を取得します。

素数を適切に処理するには、追加の if が必要であることに注意してください。素数の場合、因数が見つからないため、カウンターは 0 になります。この場合、ループの後に 1 に設定する必要があります (1 つの因数: それ自体)。

于 2012-04-12T16:00:33.597 に答える