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为所有素数添加一个循环，它只是告诉我这个素数在列表中出现了 n 次。
任何更好的方法来获得整数的单个素数的数量。

4

2 回答 2

1

是的，正如@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（一个因子：自身）

于 2012-04-12T16:00:33.597 回答