---

埃拉托斯特尼筛法

#define ll long long
const int maxn = 1e5 + 5;
int vis[maxn], prime[maxn];
void Prime(int n){memset(vis,0, sizeof(vis));//标记是否为素数memset(prime, 0,sizeof(prime));//存素数int cnt = 0;vis[0] = vis[1] = 1;//0和1都不是素数for (int i = 2; i <= n; i++) {if (!vis[i]) {//如果是素数就存prime[++cnt] = i;}for(ll j = 1LL*i*i ;j <= n; j+=i) vis[j] = 1;}
}

​ 假设 $2$ 到 $n$ 全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数。把这些合数都筛掉就能得到所有的素数。其时间复杂度为 $O(n\log{\log{n}})$。但仔细分析能发现，这种方法会造成重复筛除合数，影响效率。
比如 $16$ 在 $i = 2，j = 2*8$ 的时候筛出过一次 ，但在 $i = 4$ ，$j= 4*4$ 的时候也被筛出了一次，所以为了解决这个问题就有了更快的线性筛法

线性筛法

#define ll long long
const int maxn = 1e5 + 5;
int vis[maxn], prime[maxn];
void Prime(int n){memset(vis,0, sizeof(vis));memset(prime,0,sizeof(prime));int cnt = 0;for (int i = 2;i <= n; i++) {if (!vis[i]) {prime[++cnt] = i;}for (int j = 1; j <=cnt && i*prime[j] <= n; j++) {vis[i*prime[j]] = 1;if (i % prime[j] == 0)  break;}}
}

​ 相对于埃式筛，线性筛的实现是让每个数都被它的最小质因数筛去，prime数组存的质数是从小到大 所以我们筛去的合数就是 i * prime[ j ] ，代码的关键在于 i % prime[ j ] == 0 这个条件 ，对于一个 $c=a*b$ ( $b$ 为 $c$ 的最小质因数 ），当通过该算法的循环循环至 $c*b$ 时，易得此时 $c\%b==0$ ，如果此时继续循环至b后面的一个素数 $d$ ，则有$c*d=a*b*d=(a*d)*b$，因为 $d>b$ ，所以$a*d>c$。当循环从 $c$ 继续查找到 $a*d$ 时我们发现当 $a*d$ 再次与素数 $b$ 想乘时，就又对 $c*d$进 行了一次操作，出现了冗余，所以在 i % prime[ j ] == 0成立时要将该层循环break掉；举例说明则是：12应该由2 * 6筛掉，而不是被3 * 4筛掉(素数2<素数5)。线性筛法速度很快时间复杂度为$O(n)$。实在不明白可以手动模拟下，在不明白可以背下来，反正也很短。