用质数的幂次表示n!的算法

Question

如何用最简单和最有效的逻辑将n！表示为质数幂的乘积？

我更感兴趣的是找到质数的幂次，以便我可以知道因子的数量。 由于n！可以表示为p1 ^ e1 * p2 ^ e2 * ... * pk ^ ek，其中每个p都是质数，则n的因子数为(e1 + 1) (e2 + 1) ... *（ek + 1）

- makmakjay45

---

欢迎来到 Stack Overflow！你尝试过什么？ - Oliver Charlesworth

你所需要做的就是找到范围在1到n内每个数字的质因数分解。如果你能分解一个整数，那么你就完成了。 - David Heffernan

@OliCharlesworth，我认为David Heffernan刚才提到的方法是可行的，但考虑到这是连续数字的乘积，可能有更高效的方法。我是stackoverflow的新手，如果违反了一些规则，请见谅。 - makmakjay45

我不确定这是否是最有效的解决方案。所以我不能自信地回答。把问题留在这里，看看是否能得到一个好的答案。不需要着急。 - David Heffernan

哈哈，你是Stack Overflow的新手，显然在问作业问题，但你知道如何在评论中使用@用户名回复。无论如何，对于一个有趣的问题，我给你点赞。 - goat

Answer 1

在我所知道的方法中，找到n!的质因数分解最有效的方法是计算每个质数在n!中出现的次数。显然，不会出现比n更大的质数，因此假设p <= n为一个质数。

在数字1, ..., n中，有

q1 = floor(n/p)

这些是p的倍数。其中包括：

q2 = floor(q1/p) = floor(n/p²)

其中包括 p² 的倍数。

q3 = floor(q2/p) = floor(n/p³)

是 n! 中 p 的指数，p³ 的倍数等等。

q1 + q2 + q3 + ...

（当 b 不被 p 整除时，a = p^k*b 对指数的贡献为 k，并出现在对应于计数 q1, ..., qk 的 k 个列表中。） 我们可以简洁地编写一个函数：

unsigned long long factorial_exponent(unsigned long long n, unsigned long long p) {
    unsigned long long exponent = 0;
    do {
        n /= p;
        exponent += n;
    }while(n);
    return exponent;
}

使用 floor(log n/log p) + 1 次除法，因此，如果已知不超过 n 的质数，则大约会贡献

log n * ∑ (1/log p + 1) ≈ 2n/log n
       p≤n

对于总工作量的划分和增加（注意：由于大多数小于等于n的质数都大于√n，因此对于质数p > √n，显然q2 = 0，直接计算它们的指数n/p更快，可以将所需除法数量减少约一半）。

如果您已经有良好的实现，则最好使用筛法找到不超过n的质数。 Atkin筛法在O(n)或O(n/log log n)次操作中完成（取决于实现方式，但对于可行的范围，log log n可以被认为是一个常数），否则使用埃拉托斯特尼筛法，它很容易实现，并且根据实现的不同，可以在O(n*log log n)或O(n)次操作中找到不超过n的质数。

该算法的总工作量受到查找质数的影响（但对于可行的n来说，确定指数的贡献仍不可忽略）。

另一方面，对于每个k ≤ n的素数分解所需的工作量当然取决于所使用的算法。对于此，使用试除法将导致总工作量约为c*n^1.5/log n（我并没有做任何确定常数c的事情，并且根据细节，您可能在分子或分母中具有log n因子，但基本上是n^1.5）。找到因子的更好方法是首先使用埃拉托斯特尼筛法的一种修改来找到最小素数因子[或任何素数因子]，同样需要O(n*log log n)次操作，然后使用它来找到因子分解。您可以存储因子分解，然后在处理已知质因子p的k时查找k/p的因子分解，或通过递归地查找k/p的已知素因子q，然后查找k/(p*q)等，直到完整的因子分解完成-如果已知的质因子始终是最小的，则这样处理要简单得多。

平均而言，k的素因子分解包含≈ log log k项，因此该方法将导致总体复杂度为O(n*log log n)。但是，该方法中的常数因子比第一个方法大得多，因此即使质数查找给出相同的复杂度，第一个方法也更快。

- Daniel Fischer

---

如果我有资格理解答案，我希望我能够进行评分。目前的SO评分系统是失灵的 - 这个答案应该得到比它现在多得多的分数。 - user82238

@BlankXavier 相信我，这是值得点赞的；) 是的，有些（太多）答案获得的点赞数比它们应该得到的要少，但其他一些答案获得的点赞数则更多。也许从长远来看它会被抵消掉。 - Daniel Fischer