Java中的因素

Question

我试图计算n的​阶乘的素数因子的列表，它的素因子按增加的顺序排序，每一个因子在这个列表中的次数与它在阶乘的素因式分解中出现的次数一样多。

我有一个程序，它计算素数的链接列表，但我不知道如何实现它，同时追加当前被乘到阶乘中的整数的素数因子：

Answer 1

public static List<Integer> getFactorialPrimeFactors(int n)
{
    List <Integer> primes = primeNum(n);

    ArrayList <Integer> primeDivisors = new ArrayList<>();
    for(int i: primes)
    {
        int count = 0;
        for(int num = i; num <= n; num *= i)
        {
            count += n/num;
        }

        while(count > 0)
        {
            primeDivisors.add(i);
            count--;
        }
    }

    return primeDivisors;
}

解释- https://math.stackexchange.com/a/642220

Answer 2

假设您已经计算了来自2.N的所有素数，并调用这个集合P，那么对于P中的每个p，您可以从E 1102.N2.N2.N检查<>E 112p<代码>E 213划分<代码>E 114n<代码>E 215并将其放到链接列表中。如果你更多地思考一下MT756在上面的评论中说了些什么，你就可以让算法更快一些。我没有使用java代码来使这个任务对您来说有点有趣。：)

Answer 3

您还应该有一个方法来计算一个数字的素数，并将它作为一个列表返回。传入从primeNum获得的素数列表，它将素数列表返回到一个数字。

public static List<Integer> primeFactors(int number, List<Integer> primes) {
    List<Integer> ans = new ArrayList<>();
    // test condition includes number >= primes.get(i)
    // so the loop exits when the current prime is greater than the number
    for(int i = 0; i < primes.size() && number >= primes.get(i); i++){
        while(number % primes.get(i) == 0){
            ans.add(primes.get(i));
            number = number / primes.get(i);
        }
    }
    return ans;
}

然后，在您的主方法中，您可以编写一个for循环，它遍历从1到n的所有数字，并调用这个primeFactors方法每一个循环。迭代调用此方法获得的结果，并将这些素数添加到列表中。最后，如果您希望将数字排序，则可以对列表进行排序。

List<Integer> primes = primeNum(n);
for(int i = 1; i <= 10; i ++){
    List<Integer> temp = primeFactors(i,primes);
    for(int j = 0; j < temp.size(); j++){
        list.add(temp.get(j));
    }
}