声明：本文所涉及部分内容可能并非原创。如发现本文侵犯了您的权益，可申请博主删除。

嘛……好久没有写博客了，今天无聊来写一篇~

为什么要写这个呢？因为这个算法让我知道了我什么都不会啊……

闲话少说，切入正题。

1. 筛素数

素数即质数，定义就不说啦

那么我们经典的筛素数的方法呢都很简单，开一个bool数组，从1到$\sqrt n$，如果是素数就把这个数的倍数给筛掉。

时间复杂度显然：$O(nlog_n)$

代码也很简单：

void prime(int n) {    for(int i = 2; i * i<= n; i++)        if(!p[i])            for(int j = i+i; j <= n; j += i) p[j] = true;}//p[i]=false：该数是素数；p[i]=true：该数不是素数 

View Code

//很久以前写的，风格比较迥异QWQ

但是显然，这样的筛素数效率并不高。比如12，在2*6时被筛了一次，在3*4时又被筛了一次。

显然筛素数的算法是有优化空间的。于是，便有了线性筛素数

2. 线性筛素数

又叫欧拉筛法。那么这种方法是怎样提高筛素数的效率的呢？

我们知道，每个合数都是由若干个质数乘积组成的，故都有一个最小的质因子。（如6=2*3，2就是6的最小质因子）

用这个因子把合数给筛掉，可以达到线性时间。

具体来看一下代码：

void prime_2(){    for(int i=2;i<=n;i++)    {         if(!p[i]) prime[++ind]=i;        for(int j=1;j<=ind;j++)        {            if(i*prime[j]>n) break;            p[i*prime[j]]=true;            if(i%prime[j]==0) break;        }    }}

代码其实也很简单，查素数表，把i*prime[j]给删掉……

等等，这句话是什么意思？

if(i%prime[j]==0) break;

其实这句话正体现了之前的思想：用最小的质因子把合数给筛掉。

prime是顺序枚举的，当prime[j]第一次是i的倍数时，说明prime[j]是i的最小质因子。

那么prime[j+1]*i一定会被prime[j]乘以某个数给筛掉。

还是举个6的例子吧。当素数枚举到2时6*2=12，把12筛掉，6%2==0，即2是6的最小质因子。那么3就没有必要再枚举了，6*3=18=9*2，2会“利用”9把18筛掉。

为什么一定会被筛掉呢？6=2*3，18=2*3*3，故18一定会被2*某个数筛掉，而没有必再用3*某个数再重复筛一遍。

而枚举到9时，2不是9的最小质因子，所以9*2=18，2一定是18的最小质因子。

这也是线性筛素数效率高的重要原因之一！ （事实上，删掉这句话对最终答案没有影响，但是效率会大大降低）

理解了上面这行代码，基本就掌握了线性筛素数。

时间复杂度自然同算法名称，是$O(n)$啦

3. 例题

3.1 问题

定义$p(x)$为$x$除1外最小的约数，定义$f(n)=\sum_{i=2}^n p(i)$

给定$n$（$2≤n<≤5*10^7$），求$f(n)$的值。

3.2 问题求解

显然这题如果用传统的筛法肯定会TLE，于是可以用线性筛求解。

在原来的线性筛基础上加2行代码就可以了。

1. 如果该数是质数，累加进ans

2. 把筛掉合数的质数累加进ans

3.3 代码

void work(){    for(int i=2;i<=n;i++)    {         if(!p[i])         {            ans+=i;            prime[++ind]=i; //1.        }        for(int j=1;j<=ind;j++)        {            if(i*prime[j]>n) break;            p[i*prime[j]]=true;            ans+=prime[j]; //2.            if(i%prime[j]==0) break;        }    }}

4. 吐槽

为何要写这个文章呢？

因为这题是一道考题，而蒟蒻的博主并不知道还有这种操作，于是只打了暴力……

最关键的是开数组时多加了俩0，硬生生的超了512M的内存限制……

QAQ

【算法学习】线性筛素数