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

Y_B_X · 2021-09-13 14:23:56 · 个人记录

设 p(i) 为 i 质因数分解后有 p(i) 个质数，

再设 mx_p(n)=\mathop{\max}\limits_{1\leq i\leq n}p(i)，这里将给出一个 mx_p(n) 的一个粗略近似。

设 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})

为了检验其精确程度，不妨打个代码试试：

#include<bits/stdc++.h>
using namespace std;
#define ld long double
const int N=5e7;
int n,m;int p[N],a[N],prm;bool b[N+10];
void init(){
    int i,j;
    for(i=2;i<=N;++i){
        if(!b[i])p[++prm]=i;
        for(j=1;j<=prm&&i*p[j]<=N;++j){
            b[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
main(){
    int i,j=1;init();
    scanf("%d",&n);
    for(i=1;i<=n;++i)scanf("%d",&a[i]);
    ld tmp=0,d,dd;
    for(i=1;i<=prm;++i){
        tmp+=log(p[i]);
        d=log(tmp);
        d=tmp/(d-1);
        if(i==a[j]){
            printf("%d  %.10Lf  %.10Lf  %.10Lf\n",i,d,i-d,d/i);
            ++j;
        }
    }
}

比如输入

10 100 500 1000 5000 10000 50000 100000 500000 1000000 3000000

可以得到这样一张表:

虽然误差 ( 第 3 列 ) 增长较快，但也不失为一个不错的近似 ( 最后一列逐渐趋于 1 )

记 s_n=\prod\limits_{i=1}^{n}p_i ，即前 n 个质数的积。

应该能证明 \lim\limits_{n\rightarrow \infty}\dfrac{n\times (\ln\ln s_n-1)}{\ln s_n}=1

由此还能推出一个 \displaystyle d(n)=\sigma_o(n)=\sum_{d|n}1 的前缀最大值近似。

由于在 n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k} 时，\displaystyle d(n)=\prod_{i=1}^k\left(\alpha_i+1\right)

所以 \displaystyle \ln(d(n))=\sum_{i=1}^k\ln\left(1+\alpha_i\right)。

而 d(n) 在 n 为 i=1,2\cdots n 中 d 最大时，\alpha_i 除较小的 p_i 外都是 1。

所以 \displaystyle \ln(d(n))=O\left(k\ln2\right)=O\left(\ln2\dfrac{\ln n}{\ln\ln n-1}\right)

所以 d(n) 近似为 O\left(\exp\left\{\ln 2\dfrac{\ln n}{\ln\ln n -1}\right\}\right)=O\left(n^{\frac{\ln2}{\ln\ln n-1}}\right)=O\left(2^{\frac{\ln n}{\ln\ln n-1}}\right)

但刚才得到的 \dfrac{\ln n}{\ln\ln n-1} 与 mx_p(n) 还是有一定误差。

且 \alpha_1，即 2 的次幂都远比 2 大。

所以用 e\times2^{mx_p(n)} 得出的结果会更加准确。

设 f_1(n)=e\times n^{\frac{\ln2}{\ln\ln n-1}},f_2(n)=e\times 2^{mx_p(n)}，下面给出一些结果：