表达n的算法！作为素数的产物

q1 = floor(n/p)

p的倍数.其中有

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

p2的倍数.其中有

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

p3的倍数.等等.在n的素因子分解中p的指数！是

q1 + q2 + q3 + ...

(a a = p ^ k * b,b不能被p整除,为指数提供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的质数最好用筛子完成,如果你已经有一个很好的实现,Sieve of Atkin在O(n)或O(n / log log n)操作中做(取决于实现,但是对于可行的范围),log log n可以被认为是常数),否则使用Eratosthenes的Sieve,它很容易实现并且找到不超过n in的素数 – 再次取决于实现 – O(n * log log n)或O(n)操作.

该算法的总工作主要是找到素数(但是对于可行的n,指数的确定的贡献仍然是不可忽略的).

另一方面,找到每个k≤n的素因数分解所需的工作当然取决于用于此的算法.使用试验除法将导致总工作量约为c * n ^ 1.5 / log n – 我没有做任何事情来确定常数c,并且根据细节,你可能在分子中有一个log n因子或分母,但它基本上是n ^ 1.5.找到因子分解的更好方法是首先在O(n * log log n)运算中修改Eratosthenes筛,找到最小的素因子[或任何素因子],然后用它来找到因子分解.你可以存储因子,然后,当用已知的素数除数p处理k时,查找k / p的因子分解,或者通过递归查找k / p的已知素因子q,然后得到因子分解. k /(p * q)等直到因子分解完成 – 如果已知的素因子始终是最小的,则处理起来要简单得多.

平均而言,k的素因子化包含≈loglog k项,因此该方法将导致O(n * log log n)总体复杂度.但是这种方法中的常数因子比第一次大得多,所以即使主要发现给出相同的复杂性,第一种也更快.