一个数的质因子个数的粗略近似

本文主要是介绍一个数的质因子个数的粗略近似，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

设 \(n\) 的质因子个数为 \(k\) ， \(n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}\)

则当每个质数都只有一次时能使 \(k\) 最大时 \(n\) 最小。

所以设 \(2\times 3\times 5\times 7\dots=n\)，

即设 \(n\) 为前 \(k\) 个质数的前缀积。

而前 \(k\) 个质数的前缀积远大于 \(k!\)

只需求出 \(k!=n\) 的近似值。

由斯特灵公式 得 \(k!\approx \sqrt{2\pi k}\left(\dfrac{k}{e}\right)^k\)

而前面的 \(\sqrt {2\pi k}\) 乘上后得出的 \(k\) 值又远小于真实 \(k\) 值

所以只需令 \(\left(\dfrac{k}{e}\right)^k=n\)

先取对数得到： \(k\ln \dfrac{k}{e}=\ln n\)

两边除 \(e\) 得： \(\dfrac{k}{e}\ln{\dfrac{k}{e}}=\dfrac{\ln n}{e}\)

即: \(\ln\frac{k}{e}\times e^{\ln\frac{k}{e}}=\dfrac{\ln n}{e}\)

由\(\text{Lambert W Function}\) 可得出 \(\ln\dfrac{k}{e}=\operatorname{W}(\dfrac{\ln n}{e})\)

所以有：\(k=\exp\left(1+\operatorname{W}(\dfrac{\ln n}{e})\right)\)

又由于 \(\operatorname W(n)=O(\ln n-\ln \ln n)\)

并且 \(\ln\dfrac{\ln n}{e}=\ln \ln n-1\)

所以 \(k=\exp(1+\ln \ln n-1+\ln (\ln \ln n-1))\)

化简得到 \(k=\dfrac{\ln n}{\ln \ln n-1}\)

所以一个数的质因子个数的一个极其粗略的近似为 \(O(\dfrac{\ln n}{\ln\ln n})\)

这篇关于一个数的质因子个数的粗略近似的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！