acwing868筛质数

筛质数一般有两种方法：埃氏筛法、线性筛法，一般用线性筛法，更快
埃氏筛法：把所有质数的倍数筛掉
线性筛法：让所有合数被他的最小质因数筛掉
如3*7=21，

• 埃氏筛法21被3和7分别操作一次
• 线性筛法21只被3操作一次

#include <bits/stdc++.h>

using namespace std;

int n;
const int N=1000006;
int prime[N],cnt=0;
bool st[N];//质数是FALSE，合数是TRUE 
void getPrime(){
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[cnt++]=i;//如果是质数就放进prime里 
        for(int j=0;prime[j]<=n/i;j++){//不需要j<cnt，因为
				//如果i是质数下面if中i 会被i自己除掉（上句话i是质数会被放入
				//如果i是合数下面的if中i会i被最小质因数除掉break，i的质因数小于他自己，所以循环到i是他的质因数已经被记入
				// prime[j]<=n/i是为了防止下面 st[i*prime[j]]里面的东西越界 
            st[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    return;
}

int main(int argc, char** argv) {
    cin>>n;
    getPrime();
    cout<<cnt<<endl;
	return 0;
}