#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> int main() { int n = 0,cnt = 0; scanf("%d",&n); bool *flag = (bool*)malloc(sizeof(bool) * n); int *pri = (int*)malloc(sizeof(int) * n); memset(flag,false,n); memset(pri,0,n + 1); for(int i = 2;i < n;i++) { if(!flag[i]) { pri[++cnt] = i; } for(int j = 1;i * pri[j] < n;j++) { flag[i * pri[j]] = 1; if(i % pri[j] == 0) { break; } } } printf("%d",cnt); return 0; }