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

用法1:筛素数

void get_prime()
{    
    int pnum = 0;
    for(int i = 2; i < MAX; i++)
    {    
        if(!vis[i]) p[++pnum] = i; 
        for(int j = 1; j <= pnum && i * p[j] < MX; j++) 
        {    
            vis[i * p[j]] = true; 
            if(i % p[j] == 0) 
                break; 
        } 
    } 
}


用法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=0。b.如果i%p!=0,那么(i+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]区间中的每一个欧拉函数值。

void solve(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
  {
        if(!vis)
        {
            p[++pnum]=i;
            phi[i]=i-1;                                                          //p为素数的结论
        }
        for(int j=1,k;j<=pnum&&(k=i*p[j])<=n;j++)
        {
            vis[k]=1;
            if(i%pris[j]==0)
            {
                phi[k]=phi[i]*p[j];                                        //如果i%p==0的结论
                break;
            }
            phi[k]=phi[i]*(p[j]-1);                                      //如果i%p!=0的结论
        }
    }
}


用法3:筛莫比乌斯函数

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

void init()
{
    miu[1]=1;                                             //根据定义0
    pnum=0;
    for(ll i=2;i<=MX;i++)
    {
        if(!vis[i])p[++pnum]=i,miu[i]=-1;   //根据定义2
        for(ll j=1;j<=pnum;j++)
        {
            if(i*p[j]>=MX)break;
            vis[i*p[j]]=1;
            if(i%p[j]==0)
            {
                miu[i*p[j]]=0;                                //根据定义3
                break;
            }
            else miu[i*p[j]]=-miu[i];                //根据定义1,2
        }
    }
}

用法4:筛最小质因子

我们给出一个结论:线性筛中每一个数字都被其最小质因子筛去。因此:

void init()
{
    miu[1]=1;
    for(int i=2;i<MX;i++)
    {
        if(!vis[i])prm[++pnum]=i,,myz[i]=i;
        for(int j=1;j<=pnum;j++)
        {
            if(i*prm[j]>=MX)break;
            myz[i*prm[j]]=prm[j];
            vis[i*prm[j]]=1;
            if(i%prm[j]==0)break;
        }
    }
}

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


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *