java中的递归素因子算法
我试图用java实现一个简单的算法,用于查找参数传递的整数的所有素数因子:
private static ArrayList<Integer> lstPrime= new ArrayList<Integer>();
public static ArrayList primeFactors(int n) {
if (isPrime(n))
{
lstPrime.add(n);
}
for (int i=2; i<=(Math.sqrt(n)); i++)
{
if (n % i == 0)
{
lstPrime.addAll(primeFactors(n/i));
return lstPrime;
}
}
return lstPrime;
}
有趣的是,如果我通过81作为n,结果将是:3,3,3,3,3,3,3,3,而它应该是:3,3,3,3(3^4=81)
# 1 楼答案
# 2 楼答案
好的!我想我已经解决了我的问题,除了ArrayList是在递归函数之外声明的。我无法想象其他任何处理列表的方法,因为这是一个递归函数,如果在函数中声明列表,那么每次递归发生时,它都会被一次又一次地实例化。以下是我到目前为止所做的,请随意批评:
例如,此代码将生成:
3,3,3,3
ForprimeFactors(81)
和5,3,2,2
ForprimeFactors(60)
等等# 3 楼答案
问题在于递归实现。使用以下命令:
# 4 楼答案
# 5 楼答案
# 6 楼答案
也许更复杂一点,但到目前为止它还可以工作,而且它使用的素数生成器可能是我在Java中能找到的最快(也是最小)的
首先,我们得到了素数生成器,需要测试一个值是否为素数。我们使用一个生成器(这个生成器比原始方法快10倍),因此我们使用缓存列表:
然后我们需要两种方法来实际获取
n
的素因子列表:最后,我们的测试用例:
例如,上述代码将生成:
而改变
n = 81
将产生所需的