欧拉筛法求质数个数和质数和

筛约数个数和

理论基础:

1、对n质因数分解 $n=p1^{k_1} * p2^{k_2} * p3^{k_3} ……$

则n的约数个数为 $(k1+1) * (k2+1) * (k3+1) …… $

2、线性筛素数时,用i和素数pj来筛掉 $ i*pj $

其中pj一定是$ i*pj $的最小素因子

如果i是pj的倍数,pj也是i的最小素因子

设t[i] 表示i的约数个数,e[i] 表示i的最小素因子的个数

A、如果i是质数,t[i]=2,e[i]=1

B、如果i不是质数,枚举已有的质数pj

$ i*pj $ 的最小素因子是pj

1、如果i是pj的倍数那么e[i]即为i中包含的pj的个数,所以$ i *pj $中包含的pj的个数为 $ e[i]+1$

所以
$ e[i * j]=e[i]+1,t[i * pj]=t[i]/(e[i]+1) * (e[i]+2) $

2、如果i不是pj的倍数,
$ e [ i * p_j ]=1,t [i * pj ]=t [ i ] * t [ pj ] $ (积性函数的性质)$ =t [ i ] * 2 $(素数的约数个数=2)

筛约数和

t[i] 表示i的约数和

e[i] 表示i的约数中,不能整除i的最小素因子的约数和

A、i是质数,t[i]=i+1,e[i]=1

B、i不是质数 i*pj的最小素因子是pj

1、如果i不是pj的倍数,那么i的所有约数中,必然没有pj的倍数

可以用反证法证明这个:设x是i的约数,且x是pj的倍数,

那么$ x=pj*b,i=x*a=pj*b*a $

即i是pj的$ b*a $倍,与i不是pj的倍数相矛盾

令S表示i的约数集,$ S_1 $ 表示i的约数翻pj倍后的数的集合

S∩S1=?,则S和S’中无重复元素

所以 $ t[i*pj]=S+S_1 =t[i]+t[i]*pj=t[i]*(pj+1) $

S’中的所有元素都能整除pj,所以$ e[i*pj]=e[i] $

2、如果i是pj的倍数,那么S和S’必有交集T

T=S中pj的倍数

所以$ i*pj $的约数和要去除交集T

那么$ t[i*pj]=S+S_1-T=S_1+S-T=t[i]*pj+e[i] $

因为pj既是i的最小素因子,有事$ i*pj $ 的最小素因子

所以 $$ e[i*pj]=e[i] $

1 thought on “欧拉筛法求质数个数和质数和”

发表评论