min25筛中g函数的必要性

前置知识min25筛学习

在学习min25筛之后我们知道有$S$函数的递推式

$$S(n,i)=g(n,|pr(n)|)-g(p{r}_i,|pr(n)|)+\sum _{j>i}\sum _{p{r}_j^k\le n}f(p{r}_j^k)\times (S(\lfloor \frac{n}{p{r}_j^k}\rfloor ,j)+[k>1])$$

其中$g(n,|pr(n)|)-g(p{r}_i,|pr(n)|)$表示$n$以内大于$p{r}_i$的质数的$f$值之和。后面相当于求$n$以内不是质数的最小质因子大于$p{r}_i$的数的$f$值之和。当$k=1$时$f(p{r}_j)$在前面已经被计算过了所以不用加1当$k>1$时$p{r}_j^k$不是质数所以要加上。

那我们想想如果改为以下式子那么$g$函数是不是就不用求了呢

$$S(n,i)=\sum _{j>i}\sum _{p{r}_j^k\le n}f(p{r}_j^k)\times (S(\lfloor \frac{n}{p{r}_j^k}\rfloor ,j)+1)$$

修改后意义不变此时不需要$g$函数$S$的值仍能正确求出那我们是否可以用这个递推式来求$S$呢

这是不行的。注意当$+[k>1]$变为$+1$时若$k=1$$p{r}_j^2>n$则$p{r}_j$也有贡献这就要求我们求出$n$以内的所有质数。一般的$n$都是$10^9$以上的级别的这显然是不可行的。

其实设置$g$函数的意义就是求$f$在大质数处的值所以$g$函数不能省去。上述的$S$的递推式虽然正确但是如果要实现的话需要求出并存储$1$到$n$的所有质数时间复杂度和空间复杂度都很大。