给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围

1≤n≤

输入样例：

8

输出样例：

4

代码：

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

const int N = 1000010;

int n,cnt;
int att[N];
int Primes[N];

int LinearFilter(int n){
    for(int i = 2;i <= n;i ++){
        if(att[i] == 0){
            Primes[cnt] = i;
            cnt++;
        }
        for(int j = 0;j < cnt && Primes[j] <= n / i;j ++){
            att[Primes[j] * i] = 1;
            if(i % Primes[j] == 0){
                break;
            }
        }
    }
    return cnt;
}

int main(){
    cin>>n;
    int res = LinearFilter(n);
    cout<<res;
    return 0;
}