3

什么是表达 n 的最简单和最省时的逻辑！作为素数的乘积？

我更感兴趣的是找到素数的幂，这样我就可以知道因子的数量。作为n！可以表示为 p1^e1 * p2^e2 * ... * pk^ek，其中每个 p 是一个素数，那么 n 的因子个数是 (e1 + 1) (e2 + 1) ... * (ek + 1)

4

1 回答 1

13

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³)

的倍数p³。p等等。所以在素数分解中的指数n!是

q1 + q2 + q3 + ...

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

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可以被认为是一个常数），否则使用 E​​ratosthenes 筛，它很容易实现并找到不超过nin 的素数 - 再次取决于实现 - 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 筛来找到最小的素因数 [或任何素因数]，然后使用它来找到因式分解. 您可以存储分解，然后在k使用已知的主要除数处理时p，查找分解k/p, 或通过递归查找已知的素因数q,k/p然后 ofk/(p*q)等来动态生成因式分解，直到分解完成 - 如果已知的素因数始终是最小的，则处理起来要简单得多。

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

于 2012-05-19T22:32:38.400 回答