1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define MAXN 1000005
using namespace std;
bool vis[MAXN];
int main(){
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int n;
    scanf("%d", &n);
    vis[0] = vis[1] = true;
    int cnt = 0;
    for(int i = 2; i <= n; ++i){
        if(vis[i]) continue;
        ++cnt;
        if(i > n / i) continue;
        for(int j = i * i; j <= n; j += i){
            vis[j] = true;
        }
    }
    printf("%d\n", cnt);
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX