莫比乌斯反俨笔记

-1.前言

0.预备知识

a.线性筛(欧拉筛)

普通筛法(埃氏筛)是O(nloglogn)的,为什么不是O(n)呢?
原因是合数可能被多个质数筛到。

于是欧拉筛诞生了。欧拉筛能满足一个合数仅被筛一次。

bool is[……];//是否质数
int tot=0,prime[……];//第i个质数
for(int i=2;i<=n;i++)
    {
        if(is[i]==0)prime[tot++]=i;
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
            {
                is[i*prime[j]]=1;
                if(i%prime[j]==0)break;
            }
    }

b.数论函数及其他

未完待续...


发表于 2019-05-25 10:59:14 in 笔记