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

概述表达n的最简单,最有效的逻辑是什么！作为素数的产物？ 我更感兴趣的是找到素数的力量,这样我才能知道因素的数量. 作为n！可以表示为p1 ^ e1 * p2 ^ e2 * … * pk ^ ek,其中每个p是素数,那么n的因子数是(e1 1)(e2 1)… *(ek 1) 找到n的素因子化的最有效方法！我所知道的是计算每个素数在n！中作为一个因素出现的频率.显然,没有大于n的素数出现,所以让p <= 表达n的最简单,最有效的逻辑是什么！作为素数的产物？

我更感兴趣的是找到素数的力量,这样我才能知道因素的数量.
作为n！可以表示为p1 ^ e1 * p2 ^ e2 * … * pk ^ ek,其中每个p是素数,那么n的因子数是(e1 1)(e2 1)… *(ek 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³)

p³的倍数.等等.在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)总体复杂度.但是这种方法中的常数因子比第一次大得多,所以即使主要发现给出相同的复杂性,第一种也更快.

总结

以上是内存溢出为你收集整理的表达n的算法！作为素数的产物全部内容，希望文章能够帮你解决表达n的算法！作为素数的产物所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。