线性筛不大全

Neck Deep / 2023-08-26 / 原文

众所周知,OI界有一股清流,它的名字叫做

筛法

这之中,有一线性筛十分出名,人称XXS.

今天稍微总结一下最近用过的,比较厉害的,线性筛.

目前用到的比较常用的线性筛,

大多是建立在质数的基础上的,

也就是以最普通的筛法求质数为基点,向外延伸.

筛法求质数

void Wonder_of_U()
{
    vis[1]=1;
    Croll(i,2,mmax)
    {
        if(!vis[i])
        {vis[i]=1;pr[++pr[0]]=i;}
        for(int j=1;j<=pr[0] && i*pr[j]<=mmax;++j)
        {
            vis[i*pr[j]]=1;
            if(i % pr[j]==0)
                break;
        }
    }
}

求一个数的最小只因数

void Wonder_of_U()
{
    vis[1]=1;
    Croll(i,2,mmax)
    {
        if(!vis[i])
        {vis[i]=i;pr[++pr[0]]=i;}
        for(int j=1;j<=pr[0] && i*pr[j]<=mmax;++j)
        {
            vis[i*pr[j]]=i;
            if(i % pr[j]==0)
                break;
        }
    }
}

筛莫比乌斯函数

void Wonder_of_U()
{
    mu[1]=1;
    Croll(i,2,mmax)
    {
        if(!vis[i])pr[++pr[0]]=i,mu[i]=-1;
        for(int j=1;j<=pr[0] && i*pr[j]<=mmax;++j)
        {
            vis[i*pr[j]]=1;
            mu[i*pr[j]]=-mu[i];
            if(i % pr[j]==0)
            {mu[i*pr[j]]=0;break;}
        }
    }
    return;
}

求一个数去掉所有平方因子后剩下的因数之积

void Wonder_of_U()
    {
        f[1]=1;
        Croll(i,2,n)
        {
            if(!vis[i])pr[++pr[0]]=i,f[i]=i;
            for(int j=1;j<=pr[0] && i*pr[j]<=n;++j)
            {
                vis[i*pr[j]]=1;
                f[i*pr[j]]=f[i]*pr[j];
                if(i%pr[j]==0)
                {
                    if(f[i]%pr[j])
                        f[i*pr[j]]=f[i]*pr[j];
                    else
                        f[i*pr[j]]=f[i]/pr[j];
                    break;
                }
            }
        }
    }

先这些,以后写(找)到了再补