****# 素数筛法****

## 试除法（暴力筛选）

```c
#include<stdio.h>//试除法(暴力筛选) 
const int N=1e7+7;
int is_prime[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=i/j;j++)//j是除数，i是被除数，遍历j从2-sqrt(i) 
        {
            if(i%j==0) is_prime[i]=1;//将合数赋值为1 
        }
    }
    for(int i = 2;i<=n;i++)
    {
        if(is_prime[i]==0) printf("%d ",i);
    }
    return 0;
} 

埃氏筛

原理是一个合数总是能分成若干个质数的乘积，换个角度理解，也可以说合数是某个质数的倍数，如果把质数的倍数都去掉了，那么剩下的就是质数了。

#include<stdio.h>//试除法(暴力筛选) 
const int N=1e7+7;
int is_prime[N];
bool isprime(int n)//定义bool函数来判断是否质数 
{
    for(int i=2;i<=n/i;i++)
    return n%i;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)//遍历从2-n的数 
    {
        if(isprime(i))//利用bool函数，如果i是素数进入下步循环(埃氏筛),根据素数倍数筛掉合数 
        for(int j=2*i;j<=n;j+=i)
        is_prime[j]=1;
    }
    for(int i=2;i<=n;i++) 
    if(is_prime[i]==0) 
    printf("%d ",i);
    return 0;
} 

## 欧拉筛

欧拉筛的核心思想是确保每个合数只被最小质因数筛掉（或者被合数最大质因数筛掉）

欧拉线性筛法求素数
时间复杂度:O(N)

先看代码,再进行解释

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N=1e6+10;
int primes[N];
bool st[N];

void get_primes()
{
int cnt=0;
//1不是质数也不是合数
for(int i=2;i<=N;i){
if(!st[i]) primes[cnt]=i;//没有被筛去,说明是质数
for(int j=1;iprimes[j]<=N;j++){
st[iprimes[j]]=true;//筛去合数
if(i%primes[j]==0) break;//核心操作,保证了O(n)的复杂度
}
}
}

int main()
{
//n以内的所有质数
int n,cnt;
cin >> n;
get_primes();
for(int i=1;primes[i]<=n;i){
cnt;
}
cout << cnt << endl;
return 0;
}

引理:算术基本定理——任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积

非常重要:1既不是质数也不是合数

显然,在所有大于0的自然数中,除了质数就是合数.要求质数,只需要”筛”去所有的合数即可.如何筛去合数,这里就应用到了算术基本定理.关于合数,这里我们需要注意两点:
(1).所有合数都要筛到
(2).不能有重复筛选,否则无法达到在线性时间内的运行了
要做到第一点,根据算术基本定理:n=q*m(q表示最小质数,m=N/q,显然m>=q),对N内的m和q进行枚举

for(某个数m;m<=N;m++){
for(小于或等于m的质数q;qm<=N;){…}
}
这样我们就保证了能枚举N以内的所有整数,然而我们还不能保证枚举的合数不重复。
先来思考一下为什么会有重复,由于对于任意一个n=mq,m和q是相对的两个状态,m大了q就变小,m小了q就变大。
设n=m1q1=m2q2,q1<=q2<=m2<=m1我们这里需要保证当且仅当在q1是最小质因数时能求解,也就是去除q2和m2的情况.因为q1与q2互质,且q1<q2,则有m2%q1=0;
所以关键步骤来了: if(i%peimes[j]==0) break;
当i是primes[j]的倍数时直接跳出循环,设i=primes[j]t,此时有iprimes[j+1]=primes[j]tprimes[j+1]
可以看到此时的最小质数时primes[j],为了避免与当m=primes[j+1]t时有重复,这里可以通过break跳过计算
此外还需注意:要保证m从2开始,因为1q=1且i%1==0;
···