1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "cstdio"
using namespace std;
int Lprim[1000010];
int vprim[1000010];
int prime(int n){
    int cont = 0;
    for(int i=2;i<=n;i++){
        if(!vprim[i]) Lprim[++cont]=i;
        for(int j=1;j<=cont;j++){
            if(i*Lprim[j]>n) break;
            vprim[i*Lprim[j]]=1;
            if(i%Lprim[j]==0) break;
        }
    }
    return cont;
}
int main(){
    int n;
    scanf("%d",&n);
    printf("%d\n",prime(n));
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX