java计算整数的素数因子中每个数字的出现次数
我想计算一个整数的每个素数因子的个数。例如,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次
获取整数的素数因子个数的任何更好方法
# 1 楼答案
yy,正如@attila和@robert所说:
我之所以使用树形图,是因为它保持了因子的自然顺序,这很整洁:) 您还可以使用一个hashmap,它应该快一点。但是素数分解的实现应该非常缓慢,以至于我认为它无关紧要:)
# 2 楼答案
每次执行
n/=i;
时,都会遇到一个因素。因此,通过在该点增加一个计数器(从0开始),您可以得到因子分解过程结束时的因子总数注意,为了正确处理素数,您需要一个额外的if。对于素数,您找不到任何因子,因此计数器将为0。在这种情况下,您需要在循环后将其设置为1(一个因子:自身)