我们已经见证了线性筛有多么强大,它强大到4·108内的所有素数可以在1.6s内求出, 而普通筛法只需要+1s 。所以这么好的一个算法,可以为你续一秒,何乐而不用呢?

用法1:筛素数



用法2:筛欧拉函数

欧拉函数是数论中重要的函数,phi(x)表示小于等于x的正整数中有几个与其互质。
以下是它的一些性质: (出现的p,q都是质数)


(0): phi(ab)=phi(a)phi(b) (a,b互质)

证明:根据唯一 分解定理,a,b均可以分解为若干个互不相同的质数的幂次之积,那么ab就是a,b的分解之积,因为a,b没有公约数,所以ab的约数个数就是(a的b的),所以phi(ab)同样满足积性。

(1): phi(p)=p-1

证明:显然。

(2): phi(ip)=pphi(i) (i%p=0)

证明:首先证明两个引理:a.如果i%p=0,那么(i+p)%(p+p)=0。b.如果i%p!=0,那么(i+p)%(p+p)!=0。这两个是显然的。所以在[1,i]这个区间中与i互质的数,同时加上i,仍旧与i+i互质,不互质的依旧不互质。所以以此类推,[1,pi]这个区间中有pphi(i)个数与p*i互质。证明完毕。(也许会有漏洞不过结论是对的)

(3): phi(ip)=phi(i)(p-1) (i%p!=0)

证明:i%p 不为0且p为质数, 所以i与p互质, 那么根据欧拉函数的积性phi(i * p)=phi(i) * phi(p) 其中phi(p)=p-1即第一条性质
由上面的4个结论,我们就可以将欧拉函数的求解插入到线性筛中,在筛素数的过程中顺便求出[1,n]区间中的每一个欧拉函数值。



用法3:筛莫比乌斯函数

莫比乌斯函数是莫比乌斯反演中的必须函数,其中miu(x)表示x的莫比乌斯函数值。
一下是它的一些性质,证明就不给出了,因为这个函数是直接定义的,而不是像欧拉函数一样通过定义求出的。
官方对μ(x)的定义是这样的:
(0):μ是一个关于整数的函数
(1):μ[x] = 1 当且仅当 x能够分解成偶数个不同质数的乘积 (其中1不能被分解,所以1的分解出的质数个数是0,所以μ[1]=1)
(2):μ[x] = -1 当且仅当 x能够分解成奇数个不同质数的乘积
(3):μ[x] = 0 除开(2),(3)的其他情况
我们也可以得到这个函数的线性筛法:

这就是我们线性筛法的主要应用~