给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1≤n≤10^6
输入样例：
8
输出样例：
4
思路：给一个数：将质数筛到的同时，筛去它的倍数，并且该倍数一定是在给定的数内的
这样在下次判定这个数是否是质数的时候直接忽略，判定下一个数。
#include<iostream>
using namespace std;
const int N=1e6+10;
int n;
bool st[N];//判断状态，该点是否被遍历过
int prime[N];//存放质数
//筛选质数
void szs(int n)
{
int cnt=0;//记录质数的个数
for(int i=2;i<=n;i++)
{
if(!st[i])//如果这个点没有被遍历过，第一次出现这个数值的话
{
prime[cnt++]=i;//存放质数
st[i]=true;
}
for(int j=0;prime[j]<=n/i;j++){
int k=prime[j]*i;//这个点是在n个数里面i的倍数
st[k]=true;//如果是i的倍数的一定不是质数，直接判定为遍历过，下次遇到就不用for循环
//直接进行下一个数值的判定
if(i%prime[j]==0)break;//在这边退出是为了保证唯一性，避免重复筛数
}
}
cout<<cnt;
}
int main()
{
cin>>n;
szs(n);
return 0;
}