CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== 筛法 ======
确定素数。
===== 埃氏筛 =====
==== 思想 ====
从每个素数出发，将其倍数都筛掉。
==== 性能 ====
每一个合数会被访问多次；复杂度$O(nloglogn)$。
==== 代码 ====
<code cpp>
for(int i=2;i<=maxn;i++)
{
    if(!vist[i])
        for(int j=i*i;j<=maxn;j+=i)
            vist[j]=1;
}
</code>
===== 线性筛（欧拉筛）=====
==== 思想 ====
对于每一个i，寻找素数使得与i的乘积中该素数为最小因子。由于每一个数的最小因子一定，该数就被唯一地访问。
==== 性能 ====
避免了重复访问；复杂度$O(n)$（？）。
==== 代码 ====
<code cpp>
for(int i=2;i<=maxn;i++)
{
    if(!vist[i])
        prime[++t]=i;
    for(int j=1;j<=t&&i*prime[j]<=maxn;j++)
    {
        vist[i*prime[j]]=1;
        if(!(i%prime[j]))
            break;
    }
}
</code>
杜教筛、min_25筛、洲阁筛学到积性函数再补。

CVBB ACM Team

用户工具

站点工具

页面工具