前置学习条件：C++11基础语法，STL(vector)

文章目的：让你记住线性筛的写法(非逻辑教学)写法教学链接：58:30开始

先上代码

int n;
cin>>n;
vector<bool> is(n+1);
vector<int> pr;
for(int i=2;i<=n;i++){
    if(!is[i])pr.push_back(i);
    for(auto x:pr){
      if(i*x>n)break;
      is[i*x]=true;
      if(i%x==0)break;
    }
}

开始默写教程
Step 1.容器：
1个素数判断数组vector<bool> is(n+1)(初始化默认为false(false状态为素数))
1个素数存放数组vector<int> pr(pr为素数英文(Prime number)前两个字母)
Step 2.线性遍历:
通过名字线性筛写出线性循环for(int i=2;i<=n;i++)
Step 3.素数存放：
如果(if)当前数是素数(!s[i])->把当前数加入素数存放数组(pr.push_back(i))
if(!is[i])pr.push_back(i);
Step 4.线性遍历+合数判断:
遍历素数存放数组(for(auto x:pr))，大数跟小数的乘积(i*x)是合数(is[i*x]=true)
for(auto x:pr){is[i*x]=true;}
Step 5.判断终止
如果(if)判断的合数(i*x)大于(>)要求的素数范围(n)，终止(break)
如果(if)大数%小数(i%x)==0，终止(break)
范围判断在前，for(auto x:pr){if(i*x>n)break; is[i*x]=true;if(i%x==0)break;}
默写一遍

1.容器：vector<bool> is(n+1);vector<int> pr; 

2.线性遍历：for(int i=2;i<=n;i++)

3.素数存放：if(!is[i])pr.push_back(i); 

4.线性遍历+合数判断：for(auto x:pr){is[i*x]=true;}

5.判断终止：if(i*x>n)break;if(i%x==0)break;
超绝练习题