Java 中的因素

Question

我正在尝试计算 n 的阶乘的素因子列表，其中素因子按升序排序，并且此列表中的每个素因子与它在素因子分解中出现的次数完全相同阶乘。

我有一个程序可以计算不超过指定数字的质数链表，但我不确定如何在将当前正在乘以的整数的质因数附加到阶乘时实现它：

Answer 1

假设您已经从 [2..N] 中计算出所有素数，并称此集合为 P，然后每个 p in P 你可以从 [2.. N]然后查看p分多少次n放入链表。如果您对 MT756 在上面的评论中所说的内容多考虑一点，您可以使我所说的算法更快一点。我放置 java 代码并不是为了让您觉得这个任务有点有趣。 :)

Answer 2

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 3

您还应该有一种方法可以计算一个数的质因数，并 returns 它作为一个列表。您传入从 primeNum 获得的素数列表，其中 returns 素数列表最多为一个数。

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;
}

然后在您的 main 方法中，您可以编写一个 forloop 循环遍历从 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));
    }
}

Answer 4

这是另一种方式。它包括多项检查以确保不必要的测试，以便尽快退出循环。如果想找到 N 阶乘末尾 0 的个数，其工作方式相同。为此，只需将 N 除以 5 的连续幂的商相加（因为 5 是 10 的较大因子）。

这是通过连续除以每个质数将 N 的商相加来实现的。

    public static List<Integer> getNFactorialFactors(int n, List<Integer> primes) {
        List<Integer> factors = new ArrayList<>();
        int nn = n;
        for (int p : primes) {
            while (nn > 1) {
                for (int i = nn / p; i > 0; i--) {
                    factors.add(p);
                }
                nn /= p;
            }
            nn = n;
        }

        return factors;
    }

Java 中的因素

Factors In Java

java

primes

factorial

prime-factoring